I had the same problem. I added this to my .emacs file:
(setq x-select-enable-clipboard t)
(setq interprogram-paste-function 'x-cut-buffer-or-selection-value)
Now Ctrl-C and Ctrl-v between Emacs and other applications work fine.
Source: Ubuntu Forums