I'm having the same problem.
So far as I can tell the issue mainly revolves around times when my EVO is on 4G. The WiFi connection seems to allow Gtalk to connect without any trouble. If I'm on 3G then it will connect fine too so long as it's not switching to 4G and/or I don't have 4G turned on.
For me the problem seems to manifest itself when I'm on 4G even if there's plenty of signal and if I'm on 3G but have 4G turned on as an option.