I have the exact same problem. Running Parallels 5.0.9344 Desktop for Mac on OSX 10.6.4 / new MacBook Pro (2.4GHz Core Duo) and Ubuntu 10.04 as the guest with Parallels Tools version 5.0.9344.558741 running.
After guest startup copy paste seems to work both ways ok. After a while it stops working. First I thought it stopped after I suspend the Mac, but today it happened after half an hour of guest boot without any suspending.
I have no other guests installed so cannot test with those.
Best,
Peter