No meu caso, a solução de andrewcaveman fez um trabalho.
I had the same issue. Tried the apt-get clean, autoclean, remove and apt-get install mysql-server-5.5 Same error would keep coming up.
I removed everything a second time, tried again, still the same problem.
This is what worked for me, though I was doing an install and not an upgrade, so I didn't care about the existing database.
I removed all the mysql application again, then I went and deleted my /var/lib/mysql directory. Keep in mind, if you have an existing database there, you will lose it. You might want to move it to another location.
After removing that directory, I installed again and it worked perfect. So something in the /var/lib/mysql directory was my problem. See if that works for you.
fonte: link