brunophp,
Você ativou os repositórios do Ubuntu? Se não ativou:
Eles não estão habilitados por padrão, e é dos repositórios que o seu Ubuntu pode ter a lista de programas para fazer download do servidor da Canonical.
Vá em Administração e entre no gerenciador de pacotes Synaptic, em uma das abas do Synaptic (me perdoa mas realmente esqueci o nome e agora não tenho como conferir) você acha a opção Repositórios, lá você marca os repositórios main, universe, multiverse e restricted. Ao mandar salvar as alterações aparece uma janela explicando o que você fez e dizendo que será preciso atualizar a lista dos pacotes, basta aceitar. Serão baixados vários pacotes e sua lista será atualizada.
Pronto.
Mais uma dica, vá em Adicionar Programas e procure pelo pacote chamado ubuntu-restricted-extras esse é um pacote que instala todos os codecs multimídia que você precisa (mp3, flash, wvm, avi, java e etc). É perfeito pra quem não quer ter problemas em ficar instalando codecs básicos.
Espero ter ajudado.
Até