Encontrou a solução.
Minha placa-mãe é a Sabertooth Asus X99. Eu tinha a inicialização segura ativada e era isso que estava estragando com o Ubuntu.
Para qualquer pessoa com o mesmo problema, veja como desativar inicialização segura para as novas Motherboards da Asus .