GUYS I HAD THE SAME PROBLEM AND NOW IM GOING TO TELL YOU HOW TO SOLVE IT!
I can only imagine how frustrated you are about this stupid issue. This is how to fix it.
I found out that it has something to do with the network your on, now don't worry I'm not going to ask you to fix or change anything related to your modem, but what you do need to do is download an application which is available for both Windows and Mac. It's called HotSpot Shield and you can easily find it in Google, but just in case here is a link to it for a Mac.
http://download.cnet.com/Hotspot-Shield/3000-2092_4-10638005.html.
Trust me it works my IPhone 3GS is half way through the update already.
I hope i have helped, if not please email me on booniprecious@hotmail.com for any other questions or trouble.