Já consegui resolver o problema!
Para quem tiver o mesmo problema, eu vou colocar como resolver:
A solução é simples. Abra o arquivo /etc/usplash.conf:
sudo gedit /etc/usplash.conf
E coloque os valores correspondentes à sua resolução. No meu caso fica assim:
# Usplash configuration file
xres=1024
yres=768
Feito isso, no terminal rode o comando
sudo update-usplash-theme usplash-theme-ubuntu
Minha resolução é 1440 x 900, mas tive que colocar a 800 x 600 pra funcionar.