iPhone 4 - untethered

If your iPhone is stuck in Recovery Mode, this fix should restore your iPhone to the factory settings, but a backup should have been created automatically when the OS was updated so you will have the option to restore from backup once the repair is made.

If iTunes is open, exit iTunes
Disconnect iPhone from computer USB
Click Start menu on desktop
Go to Control Panel
Go to Programs
Go to Programs and Features
Select Apple Mobile Device Support and click repair
Connect iPhone to computer USB (device should install automatically)
Open iTunes
When prompted, click restore iPhone
OS should install now and restore factory settings

iPhone will automatically restart when OS is successfully installed, and you will have the option to setup as new or restore from backup

Well that was a bit scary. I've just updated the firmware on my iPhone to 2.2 (the horrors!). Actually, this normally shouldn't be too much of a trial. The difference here is that I did it from Windows running inside VMWare on a Linux host.
I initially tried the naive approach of applying the update normally using iTunes (but running inside VMWware). Don't do this! The host (Linux) USB subsystem gets in the way leaving you with a somewhat useless iPhone in "recovery mode". It seems that the iPhone firmware upgrade procedure does something tricky with USB that doesn't play nicely with VMWare running on Linux.
To workaround the issue, some USB modules have to not be loaded on the Linux host during the upgrade. Extending the tips on Stephen Laniel's blog I created a blacklist file for modprobe that prevents certain USB modules from loading. Just unloading the modules manually isn't enough. The iPhone reconnects to the USB bus at least once during the upgrade process causing udev to reload the modules you've manually unloaded.
So before attempting the upgrade, create a file named something like /etc/modprobe.d/blacklist-usb with the following contents:

blacklist snd_usb_audio
blacklist usbhid
blacklist ehci_hcd

I'm not sure if ehci_hcd needs to be disabled, but I did this in my case.
Reload udev so that it knows about the new modprobe config file:

sudo /etc/init.d/udev reload

Now make sure these modules aren't already loaded:

sudo /sbin/modprobe -r snd_usb_audio
sudo /sbin/modprobe -r usbhid
sudo /sbin/modprobe -r usbhid

Now go back to VMWare, cross your fingers and attempt the firmware upgrade using iTunes. Things should progress along slowly.
You might find that at one point during the upgrade that iTunes sits there with a dialog saying "Preparing iPhone for upgrade". If this goes on for several minutes it could be that the iPhone isn't connected to VMWare anymore. iTunes is just waiting for the device to appear. If this happens, reattach the iPhone to VMWare using the "Removable Devices" option on VMWare's VM menu. It's a good idea to occasionally check that the iPhone is connected to VMWare during the upgrade.
Once the upgrade is complete you can remove the modprobe config file and reload VMWare:

sudo rm /etc/modprobe.d/blacklist-usb
sudo /etc/init.d/udev reload

For the record, this was done using iTunes 8 running on Vista running inside VMware Workstation 6.5.0 build-118166 on Ubuntu Intrepid (8.10).