Just sounds like typical VNC speed/redraw. If I may, when you're tired of VNC... try -
freeNX...It's much better than VNC
much more secure (uses key exchange across SSH)
much faster (I mean a alot!)
more feature support (like audio etc)
easy to install.
I just came across it by chance a while back. I can't say enough good things about it ..and I can't believe all the time I spent manually tunneling VNC though SSH.
cheers