vim-full foi substituído por vim-gnome . Veja a resposta de BillThor para mais detalhes.
vim é dividido em subpacotes: vim é o binário principal, vim-scripts são alguns scripts extras relacionados ao vim, vim-doc é a documentação do vim, vim-gui-common é componentes comuns da interface gráfica vim, e vim-gnome é o aplicativo específico do gnome para lançar uma versão GUI do vim.
Eles estão divididos porque nem todos querem todos esses componentes. Se eu só trabalho a partir da linha de comando e já sei como usar o vim (ou qualquer outra aplicação), então os pacotes * -gui-common e * -gnome e * -doc fazem muito espaço e tempo desperdiçados.