Tente o seguinte:
$ apt-get purge --auto-remove mysql-server-core
...<output from apt-get>...
Em geral, você deve usar apt-get
em vez de dpkg
diretamente para instalar / remover software em um Debian / Ubuntu.
Para o mysql, você também pode querer seguir o acima com isto:
$ rm -rf /var/lib/mysql