You might want to try to repair and\or reset your keychain. If that doesn't work I'd delete all your accounts from Mail and recreate them. If that doesn't work, check the Library for the Mail folder and move that to the desktop and try again. If that doesn't work, move both of the keychain files from the library to the desktop and try again.
And if that doesn't work... Switch email clients. 🙂