I had the same problem, and rebooting the machine and remove known_keys file did help me. Then, I found this thread:
http://open.eucalyptus.com/forum/ubu...nied-publickey
where is suggested to add a line on eucalyptus-cc.conf file, and now it works.

Am I wordering if it is planned to include this new line in the next UEC release, since it seems a bug.

Thanks,
Massimo