Amazon EC2 – Is the EC2 Instance ID Unique Forever?

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?

I took a look around the Developer Guide and API Reference and nowhere in either of them could I find any guarantee that the instance id would be unique among all availability zones.

The only link I could really find online (besides the one you posted) was this serverfault question which includes a post by a guy named 'jedberg' who says he contacted Amazon support and asked whether you would ever get a duplicate instance id. Their response was:

"Instance ids are unique. You'll never receive a duplicate id. However, the current format of the instance id is an implementation detail that is subject to change. If you use the instance id as a string, you should be fine."

Which doesn't specifically say that they're unique per availability zone, and does say that they make a guarantee to provide a unique instance id.

Given no concrete indication either way, I'd err on the side of caution and assume you could receive a duplicate in another availability zone. If you're really not sure, you may want to put a request in with Amazon support to ask for clarification (and post their response here!).