Uma boa tentativa para garantir que o sistema está em boa forma e não tem problemas com a instalação interrompida é invocar
dpkg --configure -a
Certifique-se de que a lista de pacotes esteja atualizada e que nenhum problema seja mostrado:
apt-get update
Opcionalmente, você pode remover todos os dados antigos antes da atualização com:
find /var/lib/apt/lists -type f |xargs rm -f >/dev/null \
O próximo passo para resolver o problema é remover o pacote linux-server por um tempo. Isso pode ser feito porque não tem conteúdo real e apenas introduz uma dependência:
This package will always depend on the latest complete Linux kernel available for Server Equipment.
dpkg --remove linux-server
Após este passo, verifique se todas as dependências atuais estão instaladas:
apt-get install -f
Se tudo for o.k. agora você pode instalar linux-server novamente:
apt-get install linux-server
Postscriptum
O linux-server está obsoleto em 12.04 . Também para equipamento de servidor o kernel genérico é usado. Veja apt-cache show linux-image-server
Package: linux-image-server...
Section: metapackages
....
Depends: linux-image-3.2.0-23-generic, linux-firmware