Teve o mesmo problema, mas teve que combinar as coisas de cima.
Etapa 1: remover o Opera
sudo apt-get purge opera-stable
Etapa 2:
sudo apt-get update
sudo apt-get clean
sudo apt-get update
sudo apt-get upgrade
Etapa 3: instalar o Opera
sudo apt-get install opera-stable