We updated the repository with 5.1.62 so unfortunately this problem is no longer reproducible.
The problem was the official repo offering another version of 5.1.62 for libmysqlclient16. The solution for this problem is to specify our version of libmysqlclient16, in this case (no longer valid):
# apt-get install percona-server-server-5.1 libmysqlclient16=5.1.61-rel13.2-430.lucid
The exact version of libmysqlclient16 can be learnt with apt-cache show libmysqlclient16.