Two things you may wish to try, to determine the cause of the issue. First of all, turn on debugging (by adding the DEBUG => 1 parameter to the new() function call), and two, check the AUTH_MODE your mail server uses. In attempting to use the first sample from the Mail::POP3Client docs, I too could not log in. When I turned on debugging, I was able to see that it was attempting to use APOP against a server that was not speaking it, and was thus failing. Setting 'AUTH_MODE' to 'PASS' (also in the new() call) resolved the issue, and the sample code worked as expected.

Hope that helps.