This error happened either because
- I tried to update the iPhone software using Organizer
- Restored the iPhone on my development machine instead of the machine that the iPhone syncs to
I finally figured out how to fix it. I used iTunes on the machine where the iPhone is synced to, and restored it to 2.2.1 OS. To do this, I had to put the iPhone in DFU mode, and shift click (Windows) in iTunes on the Restore button and select the 2.2.1 .ipsw.
Once the iPhone was restored, I updated the phone to the 3.0 OS by shift clicking on the Check Updates button in iTunes and selecting the 3.0 OS from the file browser.