Como até mesmo reinstalar o Ubuntu não mudou nada, eu pensei que algo estava errado com a própria VM. Então eu mantive meu novo (VMware Tools instalado) novo Ubuntu 9.04 VMDK e criei outra VM com as mesmas especificações (RAM, CPU, HDD) e BAM! funcionou. Então eu abri os dois no WinMerge e os comparei, e além das linhas padrão e inúteis, notei um que eu nunca ouvi falar:
svga.guestBackedPrimaryAware = "TRUE"
Ele estava presente na antiga VM (que não funciona) e não na nova. Efetivamente, depois de removê-lo da antiga VM, tudo funcionou corretamente. Eu digitei no Google e encontrei alguns tópicos aqui sobre o Grub que não queriam usar resolução máxima e coisas assim, tópicos que eu nem vi nos resultados anteriores.