Glad to hear that I'm not the only one having this issue!
I have been checking for an OTA update every day since the end of June, because I suffer from the reboot bug and am anxious to get the fix ASAP. Some time last week it stopped saying "No New Software Update Available" and just exits like what you described.
On Friday when the OTA fix was released, I got so frustrated that I couldn't get the update that I tried a factory reset on my phone. That didn't work. Then things got worse, because after the reset, Android Market was unable to download any app. Every time it would say "Download was Unsuccessful".
I tried factor reset 2 or 3 more times. I tried formatting my SD card. I tried taking the SIM card out. On Saturday I took it to the Verizon store & they said they've never seen this before, and ordered me a like-new replacement that's supposed to come next week.
In the meantime, this morning I was suddenly able to download Market apps again! Now if I can just get the OTA to work, I may not need this refurb phone they're sending me. Unless it has newer hardware or something... I am thinking I will keep my phone as long as I can figure this out.
I found another forum post where some folks had a similar issue:
Software update not working...? - Android Forums
One person there said they got the refurb phone, put their SIM in and the OTA worked right away. Then, out of curiosity, they put the SIM back into their original phone and the OTA worked that time too. It sounds like this has something to do with Verizon's OTA servers rather than the phone itself....