O mesmo problema aqui e eu tenho uma solução:
Abra um terminal e abra o arquivo avg2013flx.prerm
sudo nano /var/lib/dpkg/info/avg2013flx.prerm
Pesquise as linhas com
if which invoke-rc.d >/dev/null 2>&1; then
invoke-rc.d avgd stop
else
/etc/init.d/avgd stop
fi
e substitua ALL ocorrências com
# if which invoke-rc.d >/dev/null 2>&1; then
# invoke-rc.d avgd stop
# else
# /etc/init.d/avgd stop
# fi
Do que executar novamente
sudo apt-get remove --purge avg2013flx
Explicação:
Comentando essas linhas, o processo parou de tentar interromper o serviço. E o serviço não estava sendo executado de qualquer maneira, por isso foi possível remover o pacote.