...when we made the VNC->NX switch, we were 32 bit and running about 50 desktops on 4GB memory. So aout 82MB per user. (Surprised?)
Not really. There are many different use cases, and this memory usage is actually what we recommended a few years ago (we recommended about ~50 MiB per user). But since, the desktop and applications have started to grow. This is why we are now recommending 100-150 MiB instead. This is enough to cover a typical rich desktop with heavy applications such as OpenOffice, Firefox, Google Earth etc. But of course, for other users it may still be perfectly fine with less than that.
Regarding video: Does totem change the resolution to 320x240 before playing the video? If not, 1680x1050 is what's going to be used. I understand if this gets jerky on 2 Mbit. In general, video playback only works well on LANs.
We are regularly testing video with sound in 1024x768 on that works great, but on a LAN.