Ok. I got something to work. Here is what I was doing wrong and what I did to make it work.
I am using Putty on my local machine. And I have pageant running in my system tray to manage my keys. I know this software works because I can log into my own SSH server without any trouble.
I ran the putty logging and it appears that I needed to be sending a SSH2 key. I was trying with an SSH1 key before.
So I generated a new SSH2 key and put it in my pageant key manager. Then I put the public key into a file named authorized_keys2 on the server and it started working.