Keychain passwords broken after setting up a SSH key

I am a web developer running Coda 2.0.11 on OSX 10.8.5 (not Mavericks yet), and I recently set up a site to use public/private RSA SSH keys with Media Temple. Getting that to work was a pain, but it works well.

For the unfamiliar, you create a key pair with Terminal – one is private, one is public. You set the public key up on the server, and configure an App like Coda to use the private key to authenticate the SFTP connection. The two keys also share a password, and Coda stores that password in the Keychain as well.

The problem:

That site (with the key pairs) is now the only one I can connect to. I have 40 or more sites that mostly use SFTP (some use FTP) and I save the passwords with each of the site connection settings. Coda uses the Mac Keychain to store the passwords. Some of the sites show a saved password, some don't. Either way, if I enter the passwords again, Coda tells me that the username and password were rejected by the server.

There are a handful of sites that I can still connect to with Transmit (another Panic product), but even some of those no longer work when I KNOW the username/password combination is correct. Similarly, I can not connect to sites using Navicat (for MySQL database management, not a Panic product) and I know I was able to connect up until very recently, which makes me think this is a Keychain issue.

The sites that I can not connect to are on Media Temple, Modwest, Dreamhost, and another local hosting company, so that rules out an issue with the hosting provider.

I ran Keychain First Aid and even Repaired Disk Permissions with the Disk Utility with no improvement.

Short of scrapping my keychain and starting over again, does anyone out there have any advice or is there a Coda bug at work in here somewhere?

Thanks.