You had luck. Wife's HTC Desire stucks in "downloading...".
- kill, clear data, uninstall updates (Google Play/Market, Downloading service, Market updating service)
- change user password
- restore phone to default
- revert phone/flash to system default (using HTC updater, then applied HTC's oficial OTA updates)
And Google Play is not working. Big issue is that more services are not working, including Maps, Chrome2phone. After resetting phone to default few minutes is Market working (until it downloaded update to Google Play).
But "Talk" is working fine. Home WiFi (no restriction) or 3G. Second Android phone on same WiFi and same 3G works without issues.