Permission denied (publickey). SSH from local Ubuntu to Amazon EC2 server

The first thing to do in this situation is to use the -v option to ssh, so you can see what types of authentication is tried and what the result is. Does that help enlighten the situation?

In your update to your question, you mention "on another local Ubuntu". Have you copied over the ssh private key to the other machine?

As it hasn't been explicitly mentioned, sshd is by default very strict on permissions on for the authorized_keys files. So, if authorized_keys is writable for anybody other than the user or can be made writable by anybody other than the user, it'll refuse to authenticate (unless sshd is configured with StrictModes no)

What I mean by "can be made writable" is that if any of the parent directories are writable for anybody other than the user, users permitted to modify those directories can start modifying permissions in such a way that they can modify/replace authorized_keys.

Furthermore, if the /home/username/.ssh directory is not owned by the user, and thus the user has no permissions to read the key you can run into problems:

drwxr-xr-x 7 jane jane 4096 Jan 22 02:10 /home/jane
drwx------ 2 root root 4096 Jan 22 03:28 /home/jane/.ssh

Note that jane does not own the .ssh file. Fix this via

chown -R jane:jane /home/jane/.ssh

These sorts of filesystem permission issues will not show up with ssh -v, and they won't even show up in the sshd logs (!) until you set the log level to DEBUG.

• Edit /etc/ssh/sshd_config. You want a line that reads LogLevel DEBUG in there somewhere. Reload the SSH server using the mechanism provided by the distro. (service sshd reload on RHEL/CentOS/Scientific.) A graceful reload will not drop existing sessions.
• Try authenticating again.
• Work out where your auth facility logs go and read them. (IIRC, /var/log/auth.log on Debian-based distros; /var/log/secure on RHEL/CentOS/Scientific.)

Much easier to work out what's going wrong with the debug output which includes filesystem permission errors. Remember to revert the change to /etc/ssh/sshd_config when done!