Push has several components. The phone, the app, MS Push service, and the monitoring service. The monitoring service, if I understand the model correctly, is the server that provides the data to be pushed. If the link from the monitoring service to the push service is down, or any of the other parts, it'll fail.
I've started to think that it was a MS server problem, because there are problems with live tiles of multiple apps (AP, Weatherbug, Weather Channel, etc). But then I noticed that my HTC tile, email tile (gmail, live, yahoo, etc.), sms tile, and Spell It tile (scrabble knock off) are all working.
Mine's still bugged. I changed my location from Washington DC to Memphis over 2 weeks ago and my Live Tile is still showing Washington DC. I've even deleted Washington DC from the cities inside of the app, but can't make my Live Tile switch to Memphis to save my life. I've even deleted and reinstalled the app to no avail.