A instalação real do ubuntu-restricted-extras deve ser boa, tente instalá-lo primeiro, para os add-ons, parece que há um bug em não listá-los, eles ainda devem estar disponíveis se você procurar pelos nomes individualmente no gerenciador de pacotes sinápticos. Para o plug-in do Adobe Flash, procure o nome entre parênteses, flashplugin-installer, ect.