I've been lurking for almost a year---hi everybody---and never felt compelled to respond until today...I had this same issue and many hours on the line with tech-support later, the plan was to ship me a new (refurb) device. That worked and I've not had any issues since. the annoying thing is that no one at sprint or in one of their stores could explain what happened, why it happened or if it would happen again. They also could not explain why the new device would work.
I had not rooted my phone or done anything sketchy to it. I bought it on 10/11/09, updated to 2.1 on May 19th, updated to .6 on June 4th and it stopped authenticating on Verizon's networks somewhere around June 6-8th. Just strange...
In any event, push the issue with advanced tech support and demand a new device. They had me reload 2.1, re-activate the phone with them, roll it back to .5 (the pre-June 4th version of 2.1) and NOTHING worked to get me back on roaming networks. all in all , wicked frustrating