Só uma pergunta. Porque está insistindo no Superdownloads? Quase ninguém usa ele no linux.
Acho que seus repositórios não estão totalmente habilitados.
Sistema / Administração / Canais de software
Na primeira tela, "Disponíveis pela internet" marque os quatro primeiros: "Main, Universe, Restricted, Multiverse".
Quando clicar em fechar ele deve dar a opção para atualizar os repositórios. Atualize e tente buscar os programas novamente. O Flash deve estar disponível.
Se quiser instalar programas à moda do Windows use o "
www.getdeb.com".