Eu encontrei e removi o .deb com
LANG=en,us sudo dpkg -r gens:i386
Agora eu tenho que resolver o outro problema do cdemu / gnome (veja acima).
Finalmente encontrei uma solução (espero que ajude alguém):
Em um terminal, digite
sudo gedit /var/lib/dpkg/statoverride
exclua a linha sobre o cdemu no arquivo
root cdemu 2755 /usr/bin/cdemud
Salve. Agora você pode atualizar. (O problema era um bug natty do ubuntu )