POP3 problem on iPhone 3g with 2.2

I recently got my first iPhone, it's a new 3G which is upgraded to OS level 2.2. I've now in vain tried to add two different POP3 accounts, so that I can check my emails on the go, but it won't work. I've successfully added and used my Gmail account. What happens is that after specifying the details like server name etc, the phone starts the verifying process. After a minute or so it says it cannot connect and asks if I want to try without SSL. Here I say Yes because the accounts don't use SSL, but then the phone just hangs "Verifying..." until the screen times out and goes blank, which takes a few minutes. When I go in again, the same prompt is back asking whether I want to use SSL or not. The same thing happens for both POP3 accounts.

Any ideas?
TIA