Quit Mail. Open Keychain Access (Applications > Utilities).
Select your Login keychain. Run Keychain First Aid (Keychain Access menu > Keychain First Aid).
Put in your password and run a verify. If there's any red, select repair and run it. Run another verify to make sure the errors are fixed.
Delete all of your mail entries. In the search bar, try putting in things like "pop," "imap", "gmail", even your email address. Quit Keychain Access.
Launch Mail. Get into the preferences (Mail menu > Preferences > Accounts). Fill in the passwords for each of your accounts. Also, go to the SMTP/Outgoing server menu, and edit. Fill in the passwords there as well. Close and save. Exit mail.
Launch mail. Make sure it retrieves mail properly. Send test emails to make sure it sends properly.