I had that happen to me yesterday here in Seattle. An endless loop of scanning->connecting->authenticating->disconnecting. I mucked around quite a bit, updating PRL, rebooting, ect. Finally I got it to connect just as I went into the I-5 express lane tunnel entrance and lost the signal.
I've only had my EVO for a week, and so far the 4G just seems to be a gimmick. When it works and has a solid connection, it's great. In general though I find coverage to be very spotty and not all that useful. It chews up the battery and really doesn't seem to be all that necessary when performing standard smartphone tasks. I don't routinely stream audio or video.
Fortunately this phone has the most solid 3G connection I've ever used, routinely getting a good signal in places where my other phones would drop off EV-DO.