I've run into this issue before and rebooting the instance, I assumed, reset the /root/.ssh/authorized_keys and the /home/ubuntu/.ssh/authorized_keys files.
I've reboot the instance twice now and I'm still not able to SSH in. I just get this:
Connection closed by x.x.x.x
Any ideas?