Eu finalmente encontrei a solução.
# wget http://www.percona.com/redir/downloads/Percona-XtraDB-Cluster/LATEST/deb/precise/x86_64/libmysqlclient18_5.5.33-23.7.6-496.precise_amd64.deb
# dpkg -i libmysqlclient18_5.5.33-23.7.6-496.precise_amd64.deb
# apt-get install -f
# apt-get upgrade
E tudo está bem agora.