"+y or "*y works only if your vim supports the xterm_clipboard. Xterm is a terminal emulator for X11. Try vim --version to see if it is supported. If you see +xterm_clipboard it should work, if you see -xterm_clipboard it won't. Now there are many Linux flavours which still have the xterm_clipboard support deactivated in their repositories. Yanking via clipboard is then impossible. Note that you still have the good old unix style of yank/paste, namely select the text you'd like to yank and middle-click on the mouse where you want to paste. This should work always and is the preferred style of yank/paste in vim. Be sure to be in insert mode and type set paste if it screws up the indentation. set nopaste to leave paste mode.
To get vim with xterm_clipboard, simply download the source, make a ./configure --with-x and then a make. Now vim should support xterm_clipboard and yanking and pasting should work flawlessly also from the clipboard.