Which build of Vim are you running? This is a common symptom of
running a stripped-down "vim-tiny", "vim-nox" or "vim-minimal"
rather than the full build. I think Mint is a Debian derivative,
so you may be able to "sudo apt-get install vim-gtk" or "sudo
apt-get install vim-gnome" to install the full variant. If
they're already installed, you might have to issue
for alt in vi vim editor gvim; do sudo update-alternatives
--config $alt; done
(there might be a couple other alternatives that, if you use
them, you'd want to check).
You can verify by looking at the output of ":version" for whether
the build you're running has "+clipboard" and/or
"+xterm_clipboard" set.
-tim