Try clearing the Play Store's app cache/data, also do it for Download Manager. If you don't immediately see it in the App Manager, tap Menu>Show System.
Also, do you have a monthly mobile data limit? If so, have you hit it, or are you close?
Another thing to try is to edit your APN settings and disable IPv6 -- sometimes Google servers have problems with IPv6, oddly enough.