Are you using Windows? If so, this is what I did for my iphone 4 but not sure how it works on a Mac.
Download and save to your computer this file:
http://appldnld.apple.com/iPhone4/061-8619.20100715.4Pnsx/iPhone3,1_4.0.1_8A306_Restore.ipsw
Then open itunes and connect your phone.
When your phone shows in itunes, hold down the Shift key and click on update.
Navigate to the folder and file you downloaded and click on Open.
Your phone will now update.
That's it.