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/