Same here, on my Android Phone HTC Desire ...
I recently updated some Apps from the Market (including Adobe Reader, Angry Birds Seasons, Boat Browser, DroidWall, Layar, QuickPic), and 2 hours ago, a received my first "Advertisement Notification" :
"New app released, Mobo task killer pro"
I downloaded AirPush Detector: no application found, so the spammer application doesn't use the AirPush API.
We need to figure out which application is causing this ...