So I ran into a bit of an odd problem. The symptoms were:
I made a set of ssh keys to log into our set of webservers. The keys worked for a while then suddenly stopped working yesterday for all of the webservers. They would just be rejected by the server completely. However, if I moved the keys to another account's home directory, it worked perfectly when I tried to log in as the user.

So:
1) Keys were fine.
2) Key permissions were fine.
3) SSH was fine - I could log in as that user using the password.

I ended up checking /var/log/secure and discovered the following error:
"Authentication refused: bad ownership or modes for directory /home/userdude" (userdude is not the actual user name :D )

Turns out I had accidentally changed /home/userdude over to 777 (rwxrwxrwx). A quick google search revealed This page which suggested the home directory had to be tightened down to remove global and other write permissions: chmod go-w ~/

I ended up dropping the home directory down to 700 to simplify things.