On your computer, through wifi, try open Terminal and:
telnet imap.gmail.com 993
telnet imap.gmail.com 587
On the iPhone maybe tell it to forget the network, rejoin it and try again. Very strange that it wouldn't connect over wifi, since outgoing access is normally left open.