Quando o script prerm ou postrm de um pacote falha, geralmente sua melhor opção é editar o script em /var/lib/dpkg/info e comentar (ou às vezes ajustar) as linhas com falha. Você deve rever cuidadosamente o que essas linhas estão fazendo e tentar fazer manualmente o que elas tentaram fazer.
No seu caso, você já excluiu os arquivos que o script está tentando excluir, por isso, comente as linhas com falha em /var/lib/dpkg/info/linux-restricted-modules-2.6.28-17-generic.postrm e execute dpkg --remove linux-restricted-modules-2.6.28-17-generic .
Depois de remover o pacote ofensivo, execute apt-get -f install para concluir qualquer operação de gerenciamento de pacotes (instalar, configurar, remover,…) que estava aguardando a remoção.