I really really hate when that happens. It was driving me mad with Emacs for a while until I added this to my .emacs:

    (setq x-select-enable-clipboard t)
    (if (functionp 'x-cut-buffer-or-selection-value)
         (setq interprogram-paste-function 'x-cut-buffer-or-selection-value))