Eu tenho o mesmo problema. Por exemplo. Pode ver openjfx no Ubuntu Software Center, mas não no novo Ubuntu Software.
Parece que você ainda pode usar o Ubuntu Software Center, que ainda está instalado para mim após a atualização do 14.04. Para pessoas que tenham instalado o 16.04 limpo, você pode instalar o Software Center por: apt-get install software-center
O Ubuntu Software foi apresentado como substituto do Software Center, então acho que ele ainda deve mostrar os pacotes de alguma forma.