This is a known issue due to the complexity of correctly detecting alternatives. A manual work-around as in gcc can be applied as a temporary workaround. A full and correct handling of alternatives is very difficult and I'm open to suggestions.
** Changed in: command-not-found (Ubuntu) Status: Unconfirmed => Confirmed -- recommends packages in universe in preference to packages in main https://launchpad.net/bugs/95598 -- ubuntu-bugs mailing list ubuntu-bugs@lists.ubuntu.com https://lists.ubuntu.com/mailman/listinfo/ubuntu-bugs