Tudo bem, finalmente descobri como consertar isso, no entanto, eu ainda não sei porque é tão lento. A ROM tem que ser chamada com VisualBoyAdvance assim:
VisualBoyAdvance --flash-128k --throttle=100 --frameskip=3 Path/to/ROM
O flash-128k faz alguns jogos funcionarem melhor que outros, mas a principal opção aqui é o frameskip. Eu tentei pular 2 quadros e foi mais rápido, mas poderia ser melhor. Eu decidi usar 3 no meu eeePC, mas veja o número que funciona para você.