I've been trying to solve this for a while, but I'm admittedly quite stumped.

I just started up a new server and was setting up OpenSSH to use key-based SSH logins, but I've run into quite a dilemma. All the guides are relatively similar, and I was following them closely (despite having done this once before). I triple checked my work to see if I would notice some obvious screw up - but nothing is apparent. As far as I can tell, I haven't done anything wrong (and I've checked very closely).

If it's any help, on my end I'm using Cygwin and the server is running Ubuntu 12.04.1 LTS.

Anyways, here is the output (I've removed/censored some parts for privacy (primarily anything with my name, website, or its IP address), but I can assure you that nothing is wrong there):

$ ssh user@host -v
OpenSSH_5.9p1, OpenSSL 0.9.8r 8 Feb 2011
debug1: Connecting to host [ipaddress] port 22.
debug1: Connection established.
debug1: identity file /home/user/.ssh/id_rsa type 1
debug1: identity file /home/user/.ssh/id_rsa-cert type -1
debug1: identity file /home/user/.ssh/id_dsa type -1
debug1: identity file /home/user/.ssh/id_dsa-cert type -1
debug1: identity file /home/user/.ssh/id_ecdsa type -1
debug1: identity file /home/user/.ssh/id_ecdsa-cert type -1
debug1: Remote protocol version 2.0, remote software version OpenSSH_5.9p1 Debian-5ubuntu1
debug1: match: OpenSSH_5.9p1 Debian-5ubuntu1 pat OpenSSH*
debug1: Enabling compatibility mode for protocol 2.0
debug1: Local version string SSH-2.0-OpenSSH_5.9
debug1: SSH2_MSG_KEXINIT sent
debug1: SSH2_MSG_KEXINIT received
debug1: kex: server->client aes128-ctr hmac-md5 none
debug1: kex: client->server aes128-ctr hmac-md5 none
debug1: sending SSH2_MSG_KEX_ECDH_INIT
debug1: expecting SSH2_MSG_KEX_ECDH_REPLY
debug1: Server host key: ECDSA 24:68:c3:d8:13:f8:61:94:f2:95:34:d1:e2:6d:e7:d7
debug1: Host 'host' is known and matches the ECDSA host key.
debug1: Found key in /home/user/.ssh/known_hosts:2
debug1: ssh_ecdsa_verify: signature correct
debug1: SSH2_MSG_NEWKEYS sent
debug1: expecting SSH2_MSG_NEWKEYS
debug1: SSH2_MSG_NEWKEYS received
debug1: Roaming not allowed by server
debug1: SSH2_MSG_SERVICE_REQUEST sent
debug1: SSH2_MSG_SERVICE_ACCEPT received
debug1: Authentications that can continue: publickey
debug1: Next authentication method: publickey
debug1: Offering RSA public key: /home/user/.ssh/id_rsa
debug1: Authentications that can continue: publickey
debug1: Trying private key: /home/user/.ssh/id_dsa
debug1: Trying private key: /home/user/.ssh/id_ecdsa
debug1: No more authentication methods to try.
Permission denied (publickey).

What can I do to resolve my problem?