I apologize ahead of time for not having "the fix," but I'm experiencing the same issues with Mail, Adium, etc. The only thing that has (mostly) helped is to delete the keychain folders in the following locations:
Library/Keychains (just delete the entire folder)
and
~/Library/Keychains (delete that entire folder, too)
That will, basically, reset your password keychain for most items, and you'll have to re-enter most of them. It's been spotty, and has worked for the most part for me, but I think there might still be one keychain item that I enter each time I reset the damned thing that mucks the rest of it up.
Have you tried opening the Keychain Access application and trying the Keychain First Aid? That never worked for me (it never actually found any problems), but others report it works for them.
The last couple OS updates, apparently, have created this issue. I've just kind of given up on it for now, because I can delete everything related to my keychain, and SOMETHING is making my Mac forget each and every time.
