Had a Nexus S and experienced the same issue, which wasn't present in the Nexus One.
Though my online research, the unofficial stance was that this is a hardware defect in the product line that Samsung and Google either didn't notice or noticed too late to do anything about. The most appropriate place to complain about this would be the Google Product Forums. Here's a thread where this issue is being discussed.
http://groups.google.com/a/googleproductforums.com/forum/m/#!topic/mobile/8ODgVdPy5Wk
...an alternative would be the call Samsung up and see if they will acknowledge that its a hardware flaw.
Unfortunately, I'm not aware of any fixes for the issue, and have found that although the work around (calibration) helps, the problem either doesn't completely go away or recurs soon after. Just to confirm, the behavior I noticed was:
In programs that display compass data (like Marine Compass) rotating the phone results in a partial rotation in the sensor data, followed by an unexpected 90 degree phantom rotation, according to the phone. This puts the displayed barring out of step with the true direction the phone is pointing.
In programs that try to display the full orientation of the phone including the direction it's pointing (like Sky Map) the display is shakey, and seldom provides a true indication of where the phone's actually pointing. Smoothing options result in slightly less shake, but the difference is marginal.
In spite.of this, games that depended on changes in orientation alone (like those games with the metal ball-bearings you need to guide through a maze--Labyrinth, if I'm not mistaken) worked flawlessly.
I decided to upgrade to a Galaxy Nexus, and noticed that the compass works like it should, and Labyrinth games continue to work. Sky Map, however is still jumpy.