Não consegui resolver este problema. É uma limitação do EC2 e do servidor NX gratuito. Em vez disso, tentei alguns servidores remotos diferentes e decidi que o tigervnc é o melhor. Apenas v1.7 (atualmente em beta) tem pacotes debian. O projeto tem scripts de compilação .deb, mas aparentemente não para versões estáveis, o que é talvez o porquê de não serem pacotes em repositórios. Funciona bem, é um projeto ativo e é o melhor servidor VNC que eu tentei. O desempenho é muito melhor do que eu esperava; ter a máquina EC2 é o mesmo país que eu posso ajudar (a latência, em vez da largura de banda, pode ser a parte mais importante de uma conexão VNC decente).
Eu achei este link muito útil: link
Fora da caixa, o xfce suporta várias resoluções de tela diferentes (assim que eu mudei para tigervnc). Eu não estou usando o cliente tigervnc oficial, estou usando Jump, um cliente mac. Funciona muito bem: bom desempenho, fácil de alterar o tamanho da área de trabalho.