I was not able to solve this problem. It's a limitation of EC2 and the free NX server. Instead I tried some different remote servers, and decided that tigervnc is the best. Only v1.7 (currently in beta) has debian packages. The project has .deb build scripts but apparently not for stable releases, which is perhaps why it is not packages in repositories. It works well, it's an active project and it's the best VNC server I tried. The performance is much better than I expected; having the EC2 machine is the same country as me may help (latency rather than bandwidth may be the more important part of a decent VNC connection).
I found this link very helpful:
Out of the box, xfce supports a range of different screen resolutions (as soon as I changed to tigervnc). I am not using the official tigervnc client, I'm using Jump, a mac client. It works really well: good performance, easy to change desktop size.