Parece-me que durante a instalação, o bootloader GRUB não foi instalado na unidade / partição correta, e a BIOS está procurando no local errado. Quando você instalar o Ubuntu, ele perguntará onde você deseja que o bootloader GRUB seja instalado. Dê uma olhada no menu suspenso que é fornecido e verifique se ele está sendo instalado em seu disco rígido principal (por exemplo, /dev/sda ou /dev/hda ; pode ou não ter um número de partição posteriormente).
Além disso, verifique sua ordem de inicialização nas configurações da BIOS. Não tendo um ThinkPad na minha frente não posso ter certeza, mas alguns BIOS dão a ordem de inicialização como algo como "Disco rígido, rede, unidade óptica, dispositivo USB" e de dentro do disco rígido, por exemplo, você escolhe qual partição é a que você quer inicializar. Outras BIOS apresentam cada uma das opções de inicialização, por exemplo, se você tiver duas unidades USB conectadas, elas serão apresentadas como uma opção de inicialização e você poderá selecionar qual delas deseja experimentar primeiro.
Você pode querer tentar instalar uma versão posterior do Ubuntu, atualizar de 12.04 para 16.04 será um pouco complicado, já que as versões mais antigas foram preteridas, e você não quer tentar atualizar diretamente de 12.04 para 16.04. Para uma máquina dessa idade, o Xubuntu ou o Lubuntu são boas escolhas. Se você estiver tendo problemas com a PAE, tente uma versão não-PAE de 32 bits; a menos que você tenha 4GB de RAM, eu não me incomodaria com a versão PAE.
Já experimentou um instalador mínimo? Tente este para 16.04 LTS . Você precisará de uma conexão de rede durante a instalação; basta selecionar Lxde ou Xfce para o ambiente de área de trabalho se você precisar de uma GUI. Esta pode ser uma escolha sábia, já que você mencionou o uso de 12.04 devido a um erro de PAE