It appears that you must be running the latest version of iTunes in order to properly retrieve the iPhone Software/Firmware 1.1.1 update. If you are running iTunes 7.3.1 or earlier, you will receive a message indicating that your iPhone's software is already up-to-date.
One iPhone Atlas reader writes:
"I have held off updating to iTunes 7.4.2 due to all the other problems users had been experiencing with syncing their phone, showing up in the pane, etc. Looks like now I will have to update iTunes in order to get the newest iPhone firmware. Go figure."