Você não poderá alterá-lo no gnome-terminal, já que ele obtém as configurações do cursor usando o gconf e o vim não pode sobrescrevê-lo.
No entanto, isso é o que eu tenho no meu arquivo .vimrc, usando o gconf e ele funciona conforme o esperado, ou seja, redefine-o para o que estava antes (bloco cursor_shape). Você deve ser capaz de usar o gcr para definir o cursor no gvim independentemente.
" for gnome-terminal
au InsertEnter * silent execute "!gconftool-2 --type string --set /apps/gnome-terminal/profiles/Default/cursor_shape underline"
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 block"
au VimEnter * silent execute "!gconftool-2 --type string --set /apps/gnome-terminal/profiles/Default/cursor_shape block"