Ok, isso foi finalmente resolvido. O problema estava no desalinhamento da partição. Parece que o instalador padrão do Debian (especialmente o lenny?) Não pode fazer o alinhamento corretamente, porque quando eu verifiquei as partições que ele fez com o parted, ele relatou desalinhamento em todas elas.
Eu resolvi isso particionando manualmente o LVM com parted antes da instalação e agora todos os convidados estão aproveitando o desempenho total.