Here's a workaround for some VNC issues that may appear with Lion.
A quick search will show a growing list of users having issues with VNC in Lion. See, for example, this Apple Discussion thread.
These same issues do not exist with Leopard or Snow Leopard. In testing to make sure our network wasn't part of the problem, we tried to VNC to a system over our VPN from outside our office. Lo and behold, it worked. The same laptop on the local network would get absolutely unworkable performance on the local wired or wireless network, but would work just fine over our Cisco VPN (but using the builtin VPN options for the Mac, not the Cisco VPN client) from outside our campus. That caused us to try having the system connect to our VPN while on the local campus and sure enough it worked as well. There appears to be something about the virtual interface that's created that works whereas using the default en0 (wired) or en1 (wireless) interfaces are problematic.
We haven't deduced the actual problem just yet, but we think we're onto something related to either the virtual interface and/or the statefulness of the VPN connection.
In any case, if you're having performance problems using VNC to access another system (Mac, PC, or Linux) from a system running 10.7 and you have a VPN, try connecting to it and see if it resolves your issues.
[crarko adds: I use Apple Remote Desktop and have not observed this. Judging from the results of the search above, it does seem to be a widespread issue for VNC clients. It looks like there was a bug report files with Apple on it, but it's not clear if the issue is still present in 10.7.2. Give it a try and let us know in the comments. Also, give the proposed workaround a try if you can and see if that helps. There's an awful lot of new networking code in Lion and it's become clear that it will take some wringing out in the field before it's all working as intended.]
Mac OS X Hints
http://hints.macworld.com/article.php?story=20111014075548757