Have you tried removing the account, rebooting, and re-adding it to the phone? Are you also certain the password hasn't changed? Or maybe a server setting?
Same problem here. The only change I can think of was the recent addition of Norton Mobile. The funny thing is the failure message is showing even as e-mails arrive.