>  vim-X11-7.1.094-alt1	Requires	/etc/alternatives/packages.d
> +vim-X11-7.1.094-alt1	Requires	/usr/bin/vim-X11
>  vim-X11-7.1.094-alt1	Requires	menu >= 2.1.25-alt4

Интересная зависимость.  Она проставлась правильно:
/usr/bin/gvim -> vim-X11

У этого пакета есть аналогичная зависимость, проставленная вручную:
Requires: vim-X11-gui

По сути, в большинстве таких случаев (взаимные зависимости между
пакетами через альтернативы) вручную теперь ставить больше ничего
не надо.  Всё проставится само.