Ubuntu – Copy-and-paste is often corrupted

I have ubuntu 10.10 with the 64-bit desktop version. When I copy-and-paste into any window, including firefox, terminal, java swing app, remote desktop, often I get 4 random letters (a 32-bit value?) if I try to copy again it may work this time or I might get another corrupt sequence.

This happen more often than not. I have tried to search for a solution but it doesn't appear to be a common problem. Any suggestions on what I should try next to fix this?

It appears that copying twice helps ^C^C often works.

EDIT: I have traced the problem to using remote desktop to a tightVNC server. When this is running the copy/paste doesn't work well. When I don't that this running there is no problem.