I was having the same issue both on my GNex and my Xoom (Team EOS Nightlies), which leads me to believe it's a Play Store (sigh) issue. TiBu Market Doctor seemed to work well in both instances, though.
Sent from my Galaxy Nexus using Tapatalk
Try taking your account off market then re adding it. Had same problems on my team EOS transformer and this and it worked
Sent from my Galaxy Nexus using RootzWiki