Ok, garotos e garotas é assim que eu consertei meu problema. Instale o Ubuntu Software Center e use-o para instalar qualquer um dos seus programas de terceiros. Funcionou para mim, então vou continuar usando. Eu sei que o 16.04 ainda é novo, mas existem erros que deveriam ter sido corrigidos antes disso. Este é um deles, espero que eles consigam acertar, parece ser muito útil.