A number of people have reported difficulty in calibrating their 3G S Compass.
The documentation is rather vague in the procedure. It states:
"The compass needs to be calibrated the first time you use it, and may need to be calibrated occasionally after that. iPhone alerts you whenever calibration is needed.
Calibrate iPhone: Wave iPhone in a figure eight. You may also be asked to move away from a source of interference."
What isn't clear is "What is a figure-8?" Is it a vertical or horizontal pattern and how should the phone be oriented? Do you twist your hand, or hold it pointing in one direction.
The best (and only) clue comes from the image presented on the iPhone itself, when the Calibration message appears.
(The following explaination has been editied from my original post to correct the process description based on feedback from a reader's comment below.)
As seen in the graphic above, the phone should be held horizontally, parallel to the ground.
Pretend the iPhone is a toy car and "drive" it around the figure-8 track. This orients the phone in all directions of the compass rose. Alternatively you might hold the phone and turn yourself around twice at a steady rate, but I haven't tried this to see if it works well.
Since the above process requires you to move the phone from hand to hand (unless you are quadriple jointed and can twist a hand around twice!) for safety you may want to lay the phone on a non-metalic surface such as a table, and drive it around the figure-8 course.
NOTE: if you are near steel surfaces, or other magnetic sources, the earth's magnetic fields are distorted, the phone cannot calibrate properly, and you will continue to get the calibration message. Thus it may be difficult to calibrate in a car with all the steel components around you. Trying to use the compass while on a subway may be impossible due to the large amount of steel AND the strong magnetic fields generated by the electrified track and large drive motors.