I've noticed that the compass has trouble staying calibrated on the galaxy nexus.
interesting thing is, the compass in maps/streetview works just fine.
Anyway here is my fix and it's never failed.
Download Compass by catch:
https://play.google.com/store/apps/details?id=com.apksoftware.compass
When you open it it'll tell you to calibrate or that the calibration is wrong. you then move the phone in a figure 8 while parallel to the ground.
go back into skymap, and everything will work as it's suppose to.
as far as i can tell it'll work until the phone is shut off and then you have to do it again.
it's a little annoying but this is a sure, albeit, temporary, fix.