Perhaps it's a firewall problem.

Seriously, though, do you get a connection refused type error or does it time out? Can you telnet to other POP3 servers? (Try mail.telocity.com -- it should allow the connection, at least, I think.)

Are you running XP? Isn't there some sort of builtin firewall? Maybe it got turned on somehow. Or is this at work and your net admins did something?