Anything wanting to go full-screen in a low-ish resolution from my Windows 7 VM (i.e. 800x600) causes an epic Parallels failure, it tries to jump between full-screen, coherence, and something else about six times, then invariably gives up and crashes the app. I've told the VM that it can take the iMac full-screen if it wants to, but it doesn't seem to be able to.
I have my best luck with Fullscreen games if I put Parallels in Fullscreen mode first, and then play... I've only noticed problems like yours if I was in coherence and tried...