Насчет бубунты не скажу, но на "вешалке для шляп" (RedHat, CentOS, Fedora) это yum provides "*/<что-то-там>". Например, я знаю, что нужная мне программа называется kakayatofignya. Чтобы поискать ее по всем настроенным репам делается yum provides "*/kakayatofignya", и если что-то найдется, будет выдано имя пакета, имя репа и все прочее, что нужно чтобы поставить.
