What happens if you disable the Screen Sharing, and instead enable Remote Management?
Go to System Preferences->Sharing->Remote
Management->Computer Settings and enable VNC there and set a password for it?
Also, try using TightVNC
http://downloads.sourceforge.net/vnc-tight/tightvnc-1.3.9-setup.exeCheers,
Joel