gvim in ubuntu is slow when switching tabs or navigating lines

It's been like this forever really. Because I worked both on Ubuntu and MacOSX interchangeably I didn't care as much. Now I think maybe it's time to finally find out what is wrong with it.

THE PROBLEM: when I switch tabs or navigate the lines with arrows or J,K keys and when I do it repeatedly (as if when trying to find the right tab holding Ctrl and hitting Tab) it seems to be delaying the action. When I stop hitting the keys gvim may still be finishing the operations (for instance, I stop hitting Ctrl+Tab, gvim may switch 5 more tabs - the number depends on how long I've been hitting Ctrl+Tab - before it stops).

MacVim with similar settings in .vimrc works just fine. The delays are present both when Compiz is turned off and turned on. Any ideas?

ProblemType: Bug
DistroRelease: Ubuntu 11.04
Package: vim-gnome 2:7.3.035+hg~8fdc12103333-1ubuntu7
ProcVersionSignature: Ubuntu 2.6.39-0.5~20110427-generic 2.6.39-rc5
Uname: Linux 2.6.39-0-generic x86_64
NonfreeKernelModules: nvidia
Architecture: amd64
Date: Mon Jul 11 22:24:32 2011
ExecutablePath: /usr/bin/vim.gnome
ProcEnviron:
 LANGUAGE=en_US:en
 PATH=(custom, no user)
 LANG=en_US.UTF-8
 SHELL=/bin/bash
SourcePackage: vim
UpgradeStatus: Upgraded to natty on 2011-06-05 (36 days ago)