Make sure you have done sudo apt-get update
and sudo apt-get upgrade
on your fresh install. This guide is geared toward Ubuntu 14.04 LTS (Trusty Tahr). Most of the guide will work for earlier versions of Ubuntu with some slight changes, but 14.04 is advised.
sudo cp /home/ubuntu/.ssh/authorized_keys /root/.ssh/