Update: This procedure also worked fof the latest build update Verizon pushed out: Build Number: 4.08.605.2
The Verizon OTA update to gingerbread came out a few weeks ago for the incredible, but I had nothing but problems with it until tonight. At first try, the very first day (a nice surprise actually) it rebooted and said I was already up to date, even though the “About Phone” section of settings set I was on Android version 2.2. I let it go, my wife’s phone updating just fine in the meantime, and then begain looking into it again a week later. I had continuous problems. I cleared cache, I changed the date to initiate the download again, moved some stuff to SD storage; all with the same result: no upodate. The process often got stuck with “Rebooting now” message showing, where apparently “now” meant “not now” (clearing cache fixes this).

Here are the steps I found to work:
– Make room for download and expansion ( I had luck with 574MB of phone storage available)
– Move applications to SD card
– Clear cache on apps that have several megabytes used up (Facebook and Google+ are big cachers)
– Clear Cache
– Boot into recovery
– Press and hold Power, Choose “Restart” option
– When screen turns off, press and hold Volume Down and Power
– When the white HBOOT screen appears, use the volume button to move down to “RECOVERY.”
– Press the Power button to select “RECOVERY.”
– When the triangle and exclamation appears, hold the Volume Up and Power button at the same time.
– Using the volume button, scroll down to “Wipe cache partition” and select it.
– Select “Reboot system now”
– Change date to a few days ahead
– Check for updates again (maybe twice)
– Reboot when asked too and wait for install to happen.
– Enjoy