I have the same problem. I installed froyo the day it was available over the air, had my evo since launch day, but today the 4g failed to connect. Was on the phone with 3 levels of tech support for hours, and in the end they basically offered an appointment at a sprint tech shop.
first, 4g would not connect, the wireless settings under menu just cycled from 4g on (it wasnt ever connected) to 4g scanning, to 4g off, over and over. This killed 40% of my battery in one hour! Eventually one of their software updates did something and the 4g wireless setting said, "4g unable to start".
I reluctantly did a hard reset after 2 failed attempts to update my phone from sprints side. The cycling 4g stopped but now the message reads "4g failed".
Annoyed but **** happens.