command-not-found is what provides this package suggestion functionality. It performs fuzzy matching on the filename to try and detect typos, which appears to be what's causing these bad suggestions.
I can't reproduce the exact problem you originally described, so this may have already been fixed in a newer version of command-not-found (be sure to run "sudo update-command-not-found" first). ** Package changed: vim (Ubuntu) => command-not-found (Ubuntu) -- You received this bug notification because you are a member of Ubuntu Touch seeded packages, which is subscribed to vim in Ubuntu. https://bugs.launchpad.net/bugs/1066549 Title: package "vim" advertised to supply "gvim" but does not. Status in command-not-found package in Ubuntu: Confirmed Bug description: This is a kind of documentation bug relating to an automated feature (possibly of "alternatives") I am running Xubuntu 12.04.1, and have added package "vim" manually. When I enter the command "gvim", I get the message The program 'gvim' can be found in the following packages: * vim * vim-gnome * vim-tiny * vim-athena * vim-gtk * vim-nox Try: sudo apt-get install <selected package> Note that "vim" appears in the list. It did not provide gvim, and is not compiled to do so ("vim -g" reports "E25: GUI cannot be used: Not enabled at compile time".) It appears what I got is more like "vim-nox". ProblemType: Bug DistroRelease: Ubuntu 12.04 Package: vim 2:7.3.429-2ubuntu2.1 ProcVersionSignature: Ubuntu 3.2.0-31.50-generic-pae 3.2.28 Uname: Linux 3.2.0-31-generic-pae i686 NonfreeKernelModules: nvidia ApportVersion: 2.0.1-0ubuntu13 Architecture: i386 Date: Sun Oct 14 10:20:11 2012 InstallationMedia: Xubuntu 12.04.1 LTS "Precise Pangolin" - Release i386 (20120817.3) ProcEnviron: LANGUAGE=en_US:en TERM=xterm PATH=(custom, user) LANG=en_US.UTF-8 SHELL=/bin/bash SourcePackage: vim UpgradeStatus: No upgrade log present (probably fresh install) To manage notifications about this bug go to: https://bugs.launchpad.net/ubuntu/+source/command-not-found/+bug/1066549/+subscriptions -- Mailing list: https://launchpad.net/~touch-packages Post to : touch-packages@lists.launchpad.net Unsubscribe : https://launchpad.net/~touch-packages More help : https://help.launchpad.net/ListHelp