My port scan came up clean but there's something going on with port 25 since I installed Entourage last night and had the same problem with it. I found it suggested on gmail's settings page that you use port 587 instead of 25 so I did that and voila, it works. Now I have to figure out why I can't recieve any mail. Sheesh! I feel like I'm playing Pop-a-Mole.
Okay, got that fixed too. Moles all gone.