Para o gnome-terminal, adicione isso ao seu ~/.vimrc
(a ser criado se estiver faltando):
if has("autocmd")
au InsertEnter * silent execute "!gconftool-2 --type string --set /apps/gnome-terminal/profiles/Default/cursor_shape ibeam"
au InsertLeave * silent execute "!gconftool-2 --type string --set /apps/gnome-terminal/profiles/Default/cursor_shape block"
au VimLeave * silent execute "!gconftool-2 --type string --set /apps/gnome-terminal/profiles/Default/cursor_shape ibeam"
endif
Encontrado aqui: Altere a forma do cursor em diferentes modos .
EDITAR
Altere o último ibeam
para block
, para sair com um cursor de bloco.