I've experienced this as well. My work-around (rather than restarting Windows) is to go run the Parallels Tools Center (C:\Program Files\Parallels\Parallels Tools\ParallelsToolsCenter.exe) and Disable then Enable Clipboard Synchronizing. This really should be addressed by the Parallels folks since clipboard sharing is one of the most useful features of Desktop for Mac.
Mark