This would normally point to an incorrect password but as you say this is not the case. If you are still having problems, it could be that your password has somehow become corrupted. Try changing it in My Account.
You may have "Log on using Secure Password Authentication", or "My server requires authentication" checked, when you may not need to. Try to uncheck one of these at a time and hit the Send/receive button to see if you get that message.
Tools - Accounts - your account - Properties - Servers