Not sure if it's a machine configuration but I have noticed on my Nexus One, I cam not able to get mail to my client using either Trademe WiFi or the McDonads free WiFi. I wonder if their routers have port 110 blocked for some reason?
Out of interest I was also in range of Cafenet so switched to that and mail came in fine.
This seems like a strange port to be blocking if indeed that is the case. I can imagine all the rugby world cup people arriving with their smartphones and finding they are unable to get mail on them using the native client.