I would try the two following things, in this order. Close Mail, then do them, then re-open Mail.
1) Run Disk Utility from the utilities folder and repair permissions on the drive.
2) Try opening the keychain assistant program (look in the utilities folder or spotlight it). When you open it, in the menus, you will find an option to do "first aid" or repair the login keychain. Try that. It sounds like Mail has somehow become disenfranchised from the login keychain, which is supposed to store these passwords for you.