De alguma forma eu resolvi isso alguns dias atrás, mas não ficou claro como eu fiz isso. De qualquer forma, o problema ocorreu novamente hoje, ao atualizar. Eu encontrei um site em japonês que mostrava a resposta:
$ which update-alternatives
/usr/bin/update-alternatives
$ sudo which update-alternatives
/usr/local/bin/update-alternatives
$ sudo mv /usr/local/bin/update-alternatives /usr/local/bin/update-alternatives.old
$ sudo apt-get upgrade
Reading package lists... Done
Building dependency tree
Reading state information... Done
0 upgraded, 0 newly installed, 0 to remove and 0 not upgraded.
2 not fully installed or removed.
After this operation, 0B of additional disk space will be used.
Do you want to continue [Y/n]? y
Setting up flashplugin-installer (11.1.102.62ubuntu0.10.10.2) ...
Downloading...
...
Flash Plugin installed.
Então, muito tempo, é que havia duas diferentes alternativas de atualização, e eu só tinha que ter certeza de que estava rodando o "correto".
Mike