I have finally upgraded to 10.7.3. Pretty much the same problem.
Case 1 using Vine VNC Server
1. On Mac install Vine VNC Server. I set the port to something other than the regular VNC port to prevent standard port hacking. I have an 8-character VNC password.
2. On PC (I have Windows 7) install RealVNC free version. I set the Color Level to Full <-- this is essential.
3. The viewer can now connect to Mac with the right VNC password. My current testing is with a foreground user already logged in. This is the common usage of VNC anyway.
4. Play around and quit RealVNC.
5. Repeat 3 and 4 a few times. Eventually VNC View will not be able to connect giving "unknown message type" error.
This behavior is the same in 10.7.2 and 10.7.3. Once the error occurs it will not work consistently until Vine Server is restarted.
I have also tried free Mocha VNC Viewer on iPad/iPhone. Same behavior.
Case 2 Using Screen Sharing
1. On Mac turn on screen sharing with a strong 8-character password.
2. On Windows 7 use Real VNC Viewer (same color level as above) to connect to Mac
3. After entering password, got a gray screen with login prompts (see my screen dump above). Tried entering username / login at this screen. No response whatsoever.
4. Moving the cursor around inside the gray screen area causes the Mac's cursor to turn to a color wheel in response to the mouse movement on PC side.
5. The top right corner of the gray screen (not captured in above screen dump) is a clock. The time displayed never changes.
I conclude Mac is not using standard and correct VNC protocol. There is not much we can do on our ends.