Hm. My first thought would be a CMYK/RGB issue, but you say you have checked that.
Without a sample file, all I can ask is if you can reproduce the error with all new files? Create a new file, draw a new object out two, and paste them into another new document. Does the error persist?