Existe um bug atual aberto para este localizado aqui e também estava presente é 12.02 LTS como visto aqui . As etapas listadas na parte inferior do relatório de erros de Anders Hall funcionam para a AMI 14.04 LTS de 64 bits (HVM) (ami-d05e75b8 em US-EAST-1):
$ sudo apt-get update
$ sudo rm /boot/grub/menu.lst
$ sudo update-grub-legacy-ec2 -y
$ sudo apt-get dist-upgrade -qq --force-yes
$ sudo reboot
Após a reinicialização, o 14.04.2 LTS foi atualizado para o 14.04.3 LTS e sudo apt-get update && sudo apt-get upgrade
retornou 0 novos pacotes.