I've been using EC2 for a couple of projects now and I'm able to login via ssh to my Ubuntu compute instances just fine via key authentication from Mac/Windows/Ubuntu. There are a few things to remember:
* VERY IMPORTANT: set up your Amazon Security Groups to permit inbound SSH connects on port 22. If you forget this step, the default configuration is to block all inbound connections.
* For an ubuntu image, you log in as user "ubuntu" using the certificate. If you try to login as root, you get a message instructing you to login as ubuntu instead.
* Remember to specify your private key when you try to ssh in. On windows, when using puTTY, you have to get puttyGen and convert the PEM file to the PPK format. I would encourage you to revisit this step, make sure you are using the private key, not the public one, and make sure you are exporting the right type of file to the right place and also remembering to browse for this file in puTTY when setting up your connection.
* As for Red Hat images, MAKE SURE YOU USE AN OFFICIAL IMAGE. If you are just grabbing one out of the community AMIs you have no idea if the machine might be compromised or not. Red Hat made an announcement
some time ago about there official cloud offerings.