First time SSH user having trouble with key pair - "No more authentication methods to try"


I am using OpenSSH for Windows 3.8.1 and trying to connect to an SSH server using public key authentication. I generated my key pair on an Ubuntu box and sent my public key to the person running the server. They have installed it in authorized_keys. I know my passphrase for the private key (I have checked it by resetting it with ssh-keygen).

When I try to connect to the server and enter my passphrase, I get an error message "No more authentication methods to try."

The command I am running is:
ssh -v -i id_rsa myusername@theserver
The file id_rsa is in the same directory as ssh.exe and so is the public key I have also placed copies in my home directory.

The output I get is:

OpenSSH_3.8.1p1, OpenSSL 0.9.7d 17 Mar 2004
debug1: Reading configuration data /etc/ssh_config
debug1: Connecting to theserver [***.***.***.***] port 22.
debug1: Connection established.
debug1: identity file myusername_rsa type 1
debug1: Remote protocol version 2.0, remote software version OpenSSH_4.2p1 Debian-5
debug1: match: OpenSSH_4.2p1 Debian-5 pat OpenSSH*
debug1: Enabling compatibility mode for protocol 2.0
debug1: Local version string SSH-2.0-OpenSSH_3.8.1p1
debug1: SSH2_MSG_KEXINIT sent
debug1: SSH2_MSG_KEXINIT received
debug1: kex: server->client aes128-cbc hmac-md5 none
debug1: kex: client->server aes128-cbc hmac-md5 none
debug1: SSH2_MSG_KEX_DH_GEX_REQUEST(1024<1024<8192) sent
debug1: expecting SSH2_MSG_KEX_DH_GEX_GROUP
debug1: SSH2_MSG_KEX_DH_GEX_INIT sent
debug1: expecting SSH2_MSG_KEX_DH_GEX_REPLY
debug1: Host 'theserver' is known and matches the RSA host key.
debug1: Found key in /home/myprofilename/.ssh/known_hosts:1
debug1: ssh_rsa_verify: signature correct
debug1: SSH2_MSG_NEWKEYS sent
debug1: expecting SSH2_MSG_NEWKEYS
debug1: SSH2_MSG_NEWKEYS received
debug1: SSH2_MSG_SERVICE_ACCEPT received
debug1: Authentications that can continue: publickey
debug1: Next authentication method: publickey
debug1: Offering public key: myusername_rsa
debug1: Authentications that can continue: publickey
debug1: No more authentication methods to try.
Permission denied (publickey).

I'd be grateful if anyone could tell me where I'm going wrong. I noticed that if I omit the username from the command-line i.e.
ssh -v -i id_rsa theserver
then I am never asked for it by the server.

I also don't have a static IP address - does this matter?