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 Bugs, which is subscribed to Ubuntu. https://bugs.launchpad.net/bugs/1066549 Title: package "vim" advertised to supply "gvim" but does not. To manage notifications about this bug go to: https://bugs.launchpad.net/ubuntu/+source/command-not-found/+bug/1066549/+subscriptions -- ubuntu-bugs mailing list ubuntu-bugs@lists.ubuntu.com https://lists.ubuntu.com/mailman/listinfo/ubuntu-bugs