Your version of Vim doesn't support X, which is required for clipboard access.  By default, Ubuntu ships several builds of vim and only the GUI variant supports clipboard access.  I always recompile vim from source so that a single vim (with symlinks for gvim etc) supports everything required (including :gui to switch from command line to GUI version).  It's really very easy to do:
# Get the compile-dependencies of vim
sudo apt-get build-dep vim
# If you haven't got mercurial, get it
sudo apt-get install mercurial
# Get the source
hg clone https://vim.googlecode.com/hg/ vim_source
# Compile it
cd vim_source
./configure \
    --enable-perlinterp=dynamic \
    --enable-pythoninterp=dynamic \
    --enable-rubyinterp=dynamic \
    --enable-cscope \
    --enable-gui=auto \
    --enable-gtk2-check \
    --enable-gnome-check \
    --with-features=huge \
    --with-x \
    --with-compiledby="Your Name <youremail@domain.com>" \
    --with-python-config-dir=/usr/lib/python2.7/config
make && sudo make install
That will install it in /usr/local, so make sure that's in your PATH before /usr and it will be used instead of the Ubuntu versions.