Comment 6 for bug 1336658

Why does libperconaserverclient18 package metadata not include a Provides-field with libmysqlcient18?

   Provides: libmysqlclient18

That would probably fix this issue (and I think we had that issue before) and libmysqlclient18.1 seems to do this right:

aptitude show libperconaserverclient18 :(
Package: libperconaserverclient18
New: yes
State: not installed
Version: 5.5.37-rel35.1-666.wheezy
Priority: extra
Section: libs
Maintainer: Percona Server Development Team <email address hidden>
Architecture: amd64
Uncompressed Size: 3,078 k
Depends: percona-server-common-5.5, libc6 (>= 2.4), libgcc1 (>= 1:4.1.1), libssl1.0.0 (>= 1.0.0), libstdc++6 (>= 4.1.1), zlib1g (>= 1:1.1.4)
Replaces: libpercona-server-client16
Description: Percona Server database client library
 Percona Server is a fast, stable and true multi-user, multi-threaded SQL database server. SQL (Structured Query Language) is the most popular database query language in the world. The
 main goals of Percona Server are speed, robustness and ease of use.

 This package includes the client library.
Homepage: http://www.percona.com/software/percona-server/

------

aptitude show libmysqlclient18.1

Package: libmysqlclient18.1
New: yes
State: not installed
Version: 5.6.15-25.5-759.wheezy
Priority: extra
Section: libs
Maintainer: Percona Server Development Team <email address hidden>
Architecture: amd64
Uncompressed Size: 3,537 k
Replaces: libpercona-server-client18
Provides: libmysqlclient18
Description: Percona XtraDB Cluster database client library
 Percona XtraDB Cluster is based on the Percona Server database server and provides a High Availability solution. Percona XtraDB Cluster provides synchronous replication, supports
 multi-master replication, parallel applying on slaves, automatic node provisioning with primary focus on data consistency.

 This package includes the client library.
Homepage: http://www.percona.com/software/percona-xtradb-cluster/

Other packages such as php5-mysql depend on libmysqlclient18

aptitude show php5-mysql :(
Package: php5-mysql
State: not installed
Version: 5.4.30-1~dotdeb.1
Priority: optional
Section: php
Maintainer: Guillaume Plessis <email address hidden>
Architecture: amd64
Uncompressed Size: 276 k
Depends: libc6 (>= 2.4), libmysqlclient18 (>= 5.5.24+dfsg-1), zlib1g (>= 1:1.1.4), phpapi-20100525, php5-common (= 5.4.30-1~dotdeb.1), ucf
PreDepends: dpkg (>= 1.15.7.2~)
Conflicts: php5-mysqli, php5-mysqlnd
Replaces: php5-mysqli, php5-mysqlnd
Description: MySQL module for php5
 This package provides modules for MySQL database connections directly from PHP scripts. It includes the generic "mysql" module which can be used to connect to all versions of MySQL,
 an improved "mysqli" module for MySQL version 4.1 or later, and the pdo_mysql module for use with the PHP Data Object extension.

 PHP (recursive acronym for PHP: Hypertext Preprocessor) is a widely-used open source general-purpose scripting language that is especially suited for web development and can be
 embedded into HTML.
Homepage: http://www.php.net/