Suponho que você esteja usando o layout de teclado INGLÊS (EUA). Caso contrário, consulte aqui .
Para mim, funciona com Ctrl + RIGHT_Shift + V em todos os layouts de teclado do Ubuntu 13.10.
O mesmo em LIBREOFFICE + OPENOFFICE
NÃO funciona com Ctrl + LEFT_Shift + V porque Ctrl + LEFT_shift é atribuído a uma combinação diferente nas configurações do teclado. Verifique suas configurações. Veja aqui meu exemplo: