I know we solved this but, there are many reason to why this could be caused. In your case it was that the Percona Server wanted to upgrade Mysql 5.1, which left some confusion between some configuration files that percona was using but not the Ubuntu mysql server 5.1. So removing/purging the package
mysql-server-5.1 was the solution.
The normal reaction for this would be to blame it on upstart, but after checking a lot we found the problem.
This is not the case for many mysql problems that are caused after an upgrade, either for that package or for the whole system.
It worked for Mr Nazariy, but I write this just to warn users that come here to first check other solutions. For example:
dmesg output. It usally says a lot about problems like this or at least it guides the person to where to look.
cat on log or error file in
/var/log. In this case,
cat /var/log/mysql/error.log told us something about another problem. We solved that one first and then proceeded to the one mention in the question.
Linux is very user friendly when trying to solve problems. Most of the time it will tell you the problem and solution.
When doing an upgrade, check to see if there is another instance of that service/app/anything running that might/could conflict (You might get a warning throughout the upgrade process).