After we upgraded to vSphere 4.1 we have been expirence problems with VM’s entering FullScreen mode.

The issue is that 9/10 times a VM enter FullScreen mode, you are not able to move the mouse to the bottom part of the screen and select a program or the Start option.

VMware is aware of the bug.
They say that it is resolved  in ESX 5 (next year)  – FullScreen mode should be completely redesigned.

Until then a patch is requested from PR, but no timeframe is released.
So if you have the same problem, please file a support request with VMware to speed up the process.