Passei muito tempo com o mesmo problema, agora resolvo usando o parâmetro --crtc ao chamar xrandr, ou seja:
xrandr --output LVDS1 --mode 800x600 --crtc 0
Também eu recomendo atribuir este comando aos comandos do CCSM e ligar a algumas teclas de atalho, é muito útil.
UPD: Para mim, só funciona depois desse comando:
xrandr -s 0
Mas isso faz com que o Diablo trava na alteração da resolução da tela) -: