I was having the same problem. Do you have a Linux VPS or shell access to the machine?
I had the same error, POP3 quit…..
and noticed this in /var/log/messages :
Sep 10 13:20:03 hindoogle xinetd[22171]: START: pop3 pid=28119 from=216.xxxxx
Sep 10 13:20:05 hindoogle popa3d[28119]: Authentication failed for xxxx from 216.xxxxx
Sep 10 13:20:05 hindoogle xinetd[22171]: EXIT: pop3 status=0 pid=28119 duration=2(sec)
so…. the password was wrong. I wish WordPress gave a better error message.