Update: Mountain Lion seems to have fixed all issues I've had connection to the Mac from a Windows VNC client. The solution below has only worked intermittently for me.
After upgrading my MacBookPro to OS X Lion I noticed that none of my Windows, and other non-Apple VNC clients such as TigerVNC, RealVNC or TightVNC could connect to it. Following some instructions in the Apple Support Discussions web site I installed the Onyx utility, used it to delete all the caches under the Cleaning section. After cleanup and reboot, VNC sharing works again, with TigerVNC, with iPad client etc.
Here is the download link to Onyx, I used version 2.4.0b3 which is the 10.3 MB (beta) download. You can skip the S.M.A.R.T. and system volume tests on startup.
Good luck, please comment on whether this works for you.