There seems to be an answer in the AWS forums for the fingerprint difference. I'm pasting the content here for posterity:
Hello,
I discussed with my colleagues and looks like it is a limitation from
our end to provide keypair in different format. You'll notice the
different lengths of the Amazon-generated Key Pair and the Import Key
Pair. In the case of an Amazon-generated Key Pair, the Fingerprint is
for the Private Key, while if you use Import Key Pair the fingerprint
is for your public key. Amazon does not retain a copy of the generated
Private Key, but the EC2 command line tools do provide a way to
reproduce the SSH2 MD5 fingerprint:
ec2-fingerprint-key ./testpair1-private.pem
61:26:cc:7d:2a:2c:a4:e9:fb:86:ca:ef:57:d6:68:f8:24:bc:59:cd
This should match what you see in the console for the region in which
you created the key, such as US-West-1 (North California).
Unfortunately the ec2-fingerprint-key command-line tool does not
fingerprint public keys. If you import the public key in another
region such as US-East-1, the web AWS Console will only display the
fingerprint of the public key.
Secondly, the AWS Console should be more clear on exactly what type of
fingerprint it displays, which is the "MD5 public key fingerprint as
specified in section 4 of RFC4716" (also known as SSH2 format) as
mentioned here:
http://docs.amazonwebservices.com/AWSEC2/latest/CommandLineReference/ApiReference-cmd-ImportKeyPair.html
We have already put in a feature request for the web-based AWS Console
to support the more common OpenSSH format. Unfortunately I was not
able to find any user-friendly tools to generate the SSH2/RFC4716
format fingerprint, though I did find that you can import the same
public key in your original region (with a name such as "Test2") and
match the shown fingerprint between regions.
(emphases mine)
As he mentions, I too wasn't able to locate any tool to generate the SSH2/RFC4716 format fingerprint. This at least solves the mystery of mismatching fingerprints (at least if we assume ssh-keygen -lf
gives output in the "more common OpenSSH format", please correct me if this assumption is wrong); I'm still getting a Permission denied (publickey)
when i try to ssh, but I'll assume it's not an actual key mismatch now and explore other avenues.