I started getting lots of spam messages, you know the ones "You have won an iPad !!" as soon as I started using Google Play on my Samsung Galaxy SIII (having left the Dark Side now...)
After much frustration and not a little scratching of various indiscreet bodily locations, it turns out some apps have "adware" as a component of them - surprising to see this coming from apps hosted by Google.
Found a nice gem called Airpush Detector which identifies these and allows you to wipe them from your device.