Também enfrentei esse problema e registrei um bug no launchpad: link
Minha solução foi a seguinte:
- corrija o arquivo /etc/init.d/virtuoso-nepomuk adicionando
### END INIT INFO
no final do bloco iniciado com### BEGIN INIT INFO
- retome o processo de atualização com
sudo apt-get upgrade
De qualquer forma, é um erro. Sugeri algumas maneiras de corrigir isso no launchpad, mas isso ainda não foi feito.