Parece que você pode ter se removido do grupo "sudo" - você editou os membros do seu grupo de usuários recentemente? Para usar o sudo, você precisa ser um membro deste grupo ou especificamente adicionado ao arquivo sudoers. No entanto, se você remover essa participação no grupo, apenas alguém com autoridade root poderá adicioná-lo novamente ou fazer uma alteração. Você não poderá instalar nada novo também.
Note que antes de 12.04, o Ubuntu usava o grupo "admin" ao invés do grupo "sudo", onde o Debian usava o grupo "sudo". Então, se você atualizou para 12.04, é possível que você tenha sido um membro do grupo admin em vez de sudo. Um ou ambos funcionarão, mas imagino que o "sudo" deva ser o grupo preferido para usuários administrativos.
Para confirmar se esse é o seu problema, tente digitar "grupos" em uma linha de comando no terminal. Se você não vê "admin" ou "sudo" (um ou ambos), então este é o seu problema. Se você vir um deles, talvez seja necessário editar diretamente o arquivo /etc/sudoers (como root, é claro).
Mas não se desespere, há uma maneira de contornar isso, embora não seja tão simples quanto a maioria das pessoas gostaria. Você precisará obter acesso root, o que pode ser feito na inicialização com um pouco de trabalho.
Primeiro, você precisa fazer o login em um modo de console de usuário único : aqui um bom como fazer isso. Ele diz como corrigir uma variedade de causas para o problema que você está tendo (aparentemente). É um pouco datado e usa o grupo "admin" em vez de "sudo", então substitua de acordo.