I have this problem with my Lumia 800 (currently with Telecom for repairs). My colleague has the same problem with an HTC Titan II we bought off MobiCity. I've also been into Telecom and Vodafone stores and found the same problem with the Lumia 610, 710 and Samsung Omnia.
My guess is most people haven't bothered to download a compass app, and if they have they probably haven't compared it to another compass to validate the direction.
Here's an example someone else posted: http://www.youtube.com/watch?v=r5PpE_eYuWo
As I already mentioned, my Lumia 800 is with Telecom. They have sent it for repairs twice only to have it returned with an "all clear" and this is it's third time in. I assume that means the diagnostic checker the service company is using is saying all is fine (very worrying). I even contacted the Nokia help centre who informed me they know people are having problems but no fix is planned.
I'll post back (hopefully in the next couple of days) once I get either a working phone or refund from Telecom. I suspect this will be an unfixable problem which will be great news for anyone wanting to return their Windows Phone for a full refund!

Lumia 800 (left) compass wrong, Lumia 900 (right) compass correct. Note the X,Y and Z values are the raw magnetometer values that you get inside the phone (I.e. the numbers used in application development) and since those numbers are wrong, you can guarantee it's a fault in the hardware or phone OS.