It sounds like you're pasting the contents of your primary selection rather than the clipboard. To check this you can watch the contents of your clipboards using
watch xsel -o -p (
-b flags for primary, secondary, and clipboard respectively).
Some possibly relevant stuff from the emacs wiki
X11 Copy & Paste to/from Emacs:
X copy and paste support has historically been a mess. This is relevant, as Emacs supports the various aspects of this mess.
Important for this discussion is the understanding that X generally distinguishes between two types of selection, the PRIMARY and the CLIPBOARD. Every time you select a piece of text with the mouse, the selected text is set as the PRIMARY selection. Using the copy function will place the selected text into the CLIPBOARD. Pasting using the middle mouse button will insert the PRIMARY selection, pasting using the paste function will insert the CLIPBOARD.
With this out of the way, starting with Emacs 24.1, GNU Emacs should already do the right thing here. If you dislike this behavior, there are two options you can customize:
x-select-enable-primary - default nil; set this to t if you want the Emacs commands C-w and C-y to use the primary selection.
x-select-enable-clipboard - default t; set this to nil if you want the Emacs commands C-w and C-y to use the clipboard selection.
Yes, you can have Emacs use both at the same time.