I have another issue with an iPhone 3GS. Initially it couldn't charge, this is fixed now. I figured I might as well upgrade to the latest firmware.
I tried the solutions mentioned earlier on my PC with no luck I am now trying on my Mac. The iPhone is running 4.2.1 I'm trying to update it.
First download attempt on my MBP failed.