Ambos os pacotes fornecem o mesmo aplicativo, mas compilados com diferentes dependências (por exemplo, o vim-gnome depende do libgnome2). O Vim-gtk é importante apenas para pessoas que usam o Kubuntu (ou algum ambiente de desktop leve) e não querem instalar bibliotecas do GNOME. Se você usa o desktop padrão do Ubuntu, as dependências já estão presentes e você pode usar o vim-gnome com segurança. Eu concordo que isso poderia ser confuso.