Eu tenho o mesmo problema. Quando eu instalei pela primeira vez a edição do servidor Ubuntu 12, não houve problema, mas depois de um mês ele não inicializará sem monitor e teclado.
O que fiz foi verificar o BIOS e alterar as opções de inicialização de 'não inicializar com erros para inicializar com erros'
Depois disso, meu servidor pode inicializar sem headless sem monitor ou teclado conectado. Parece que o BIOS não permitirá a inicialização se houver um erro, como nenhum monitor ou nenhum teclado. Ao permitir que o servidor ignore qualquer erro, ele será inicializado.