I mean, WTH?
I messed up the server and I had to do a brand new reinstall purging everything, I also used locate mysql to check where else mysql was hiding.
When I try to install mysql-server-5.1 apt-get throws me an error saying:
Errors where encountered while processing:
mysql-server-5.1
E: Sub-process /usr/bin/dpkg returned an error code (1)
And now it also trows me the error even if I want to install something completely unrelated to mysql!