rwatson,
If the Windows machine is running XP home edition, it won't work. That is one of those little "incentives" that Microsoft built in to get you to buy the more expensive version.
But when I was playing with this stuff, even using XP Pro, the Windows stuff seemed to be more trouble than it was worth. So I installed the Windows version of Tightvnc on the Windows machine and it worked fine, even on XP home edition.
You must understand though that I did not spend a lot of time on it. So, some of the problems I had with Windows may have just been due to my own ignorance.