AWS ssh access 'Permission denied (publickey)'

How to connect to a AWS instance through ssh?

I have:

Signed up at AWS;
Created a public key and a certificate at AWS website and saved them to disk;
Went to my console and created environment variables:

$ export JAVA_HOME=/usr/lib/jvm/java-6-openjdk/
$ export EC2_CERT=/home/default/aws/cert-EBAINCRNWHDSCWWIHSOKON2YWGJZ5LSQ.pem
$ export EC2_PRIVATE_KEY=/home/default/aws/pk-EBAINCRNWHDSCWWIHSOKON2YWGJZ5LSQ.pem
Told AWS API to use this keypair and saved the keypair to file:

$ ec2-add-keypair ec2-keypair > ec2-keypair.pem
Started an AWS Ubuntu 9 instance using this keypair:

$ ec2-run-instances ami-ed46a784 -k ec2-keypair
Attempted to establish a ssh connection to the instance:

$ ssh -v -i ec2-keypair.pem ubuntu@ec2-174-129-185-190.compute-1.amazonaws.com
OpenSSH_5.1p1 Debian-5ubuntu1, OpenSSL 0.9.8g 19 Oct 2007
debug1: Reading configuration data /etc/ssh/ssh_config
debug1: Applying options for *
debug1: Connecting to ec2-174-129-185-190.compute-1.amazonaws.com [174.129.185.190] port 22.
debug1: Connection established.
debug1: identity file ec2-keypair.pem type -1
debug1: Remote protocol version 2.0, remote software version OpenSSH_5.1p1 Debian-5ubuntu1
debug1: match: OpenSSH_5.1p1 Debian-5ubuntu1 pat OpenSSH*
debug1: Enabling compatibility mode for protocol 2.0
debug1: Local version string SSH-2.0-OpenSSH_5.1p1 Debian-5ubuntu1
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 'ec2-174-129-185-190.compute-1.amazonaws.com' is known and matches the RSA host key.
debug1: Found key in /home/default/.ssh/known_hosts:11
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_REQUEST sent
debug1: SSH2_MSG_SERVICE_ACCEPT received
debug1: Authentications that can continue: publickey
debug1: Next authentication method: publickey
debug1: Trying private key: ec2-keypair.pem
debug1: read PEM private key done: type RSA
debug1: Authentications that can continue: publickey
debug1: No more authentication methods to try.
Permission denied (publickey).
What could be the problem and how to make it work?