AWS ssh access 'Permission denied (publickey)' issue

How to connect to a AWS instance through ssh?

I have:

1. Signed up at AWS;
2. Created a public key and a certificate at AWS website and saved them to disk;

3. 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
   

4. Told AWS API to use this keypair and saved the keypair to file:

   $ ec2-add-keypair ec2-keypair > ec2-keypair.pem
   

5. Started an AWS Ubuntu 9 instance using this keypair:

   $ ec2-run-instances ami-ed46a784 -k ec2-keypair
   

6. 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?