I had the same problem, wanted to control a Ubuntu machine from another with windows and it went so slow it was almost unusable.
Searching in internet didn't helped.
I I installed XFCE in the ubuntu machine, just to try the interface, and I've notices that now it works perfectly. I suppose it must be something related to GNOME (since the software used, TightVNC and the Ubuntu Repository VNC sharing desktop).
Just try it

Ubuntu 11.04 code named natty narwhal is released download ubuntu 11.04
Read ubuntu 11.10 reviews and share yours now!!