The version of gpgkey2ssh that ships with gnupg2 creates keys that appear to be
unreadable by modern versions of openssh (i've tried this with gnupg2 2.0.9 and
openssh 4.7, built from the debian packages).
RSA keys are output with the MPIs inverted (modulus where exponent should be,
and vice versa), and DSA keys use the wrong header label ("ssh-dsa" instead of
"ssh-dss").
The attached patch resolves the problem for me.
This has also been reported as debian bug 473841:
Thanks for all your work on gnupg!