It appears this problem is even worse.

There was a report that issuing a general upgrade can cause apt-get to want to
remove mariadb-server-5.5 so that it can upgrade libmysqlclient.

So a user not being careful to notice this fact could end up accidentally
removing mariadb during a routine upgrade (the data will not be removed, but
it is still a rather serious issue).

See also this knowledgebase entry:

https://kb.askmonty.org/en/drop-in-replacement-on-debian/

I wanted to update both libmysqlclient18 and mysql-common on a machine running Precise Pangolin (12.04 LTS) and run into the same issue, I think:

The following packages will be upgraded:
libmysqlclient18 mysql-common

2 packages upgraded, 0 newly installed, 0 to remove and 0 not upgraded.
Need to get 0 B/960 kB of archives. After unpacking 3,566 kB will be used.
The following packages have unmet dependencies:
libmariadbclient18 : Depends: libmysqlclient18 (= 5.5.28-mariadb-a1~precise) but 5.5.29-0ubuntu0.12.04.1 is to be installed.
mysql-common : Breaks: mysql-client-5.1 which is a virtual package.
Breaks: mysql-client-core-5.1 which is a virtual package.
Breaks: mysql-server-core-5.1 which is a virtual package.
The following actions will resolve these dependencies:

Remove the following packages:
1) libmariadbclient18
2) mariadb-client-5.5
3) mariadb-client-core-5.5
4) mariadb-server
5) mariadb-server-5.5
6) mariadb-server-core-5.5

Unfortunately, aptitude wants to remove MariaDB.

apt-cache policy libmysqlclient18 shows the following:

libmysqlclient18:
Installed: 5.5.28-mariadb-a1~precise
Candidate: 5.5.29-0ubuntu0.12.04.1
Version table:
5.5.29-0ubuntu0.12.04.1 0
500 http://de.archive.ubuntu.com/ubuntu/ precise-updates/main amd64 Packages
500 http://security.ubuntu.com/ubuntu/ precise-security/main amd64 Packages

• • • 5.5.28-mariadb-a1~precise 0
      500 http://mirror.netcologne.de/mariadb//repo/5.5/ubuntu/ precise/main amd64 Packages
      100 /var/lib/dpkg/status
      5.5.22-0ubuntu1 0
      500 http://de.archive.ubuntu.com/ubuntu/ precise/main amd64 Packages

I got this from apt-get dist-upgrade

Reading package lists... Done
Building dependency tree
Reading state information... Done
Calculating upgrade... Done
The following packages will be REMOVED:
libmariadbclient18 mariadb-client mariadb-client-5.5 mariadb-client-core-5.5
mariadb-server mariadb-server-5.5 mariadb-server-core-5.5
The following packages will be upgraded:
libmysqlclient18 mysql-common
2 upgraded, 0 newly installed, 7 to remove and 0 not upgraded.
Need to get 0 B/943 kB of archives.
After this operation, 100 MB disk space will be freed.
Do you want to continue [Y/n]?

So I've used
aptitude forbid-version libmysqlclient18=5.5.29
aptitude forbid-version mysql-common=5.5.29
to reduce the risk of installing this be accident.

I've switched to using apt-get upgrade until this is resolved.

Even after 5.5.29 release, we have a similar problem when someone attempts to replace Percona server 5.5.29 with MariaDB 5.5.29:

The following packages have unmet dependencies:
libmariadbclient18 : Depends: libmysqlclient18 (= 5.5.29-mariadb1~precise) but 5.5.29-rel29.4-401.precise is to be installed
E: Unable to correct problems, you have held broken packages.

The same workaround ( apt-get install libmysqlclient18=5.5.29-mariadb1~precise )

Its "normal" that there might be conflicts for users having both MariaDB and Percona repositories, as both are providing drop-in replacement for the MySQL that is shipped with the distribution and by default every repositories have the same priority, so if two of them have the same package, it will try to install the one that seems to be the latest.

You can choose that one of the repository has an higher priority (either for * or for a specified package), for example you can add these lines on /etc/apt/preferences or on a file on /etc/apt/preferences.d/ (in that example, mirror3.layerjet.com is the Maria repository used) :
Package: *
Pin: origin repo.percona.com
Pin-Priority: 999

Package: *
Pin: origin mirror3.layerjet.com
Pin-Priority: 1000

Or if you want for example to have percona-toolkit from the Percona repo but libmysqlclient18 from the Maria one :
Package: percona-toolkit
Pin: origin repo.percona.com
Pin-Priority: 1000

Package: libmysqlclient18
Pin: origin mirror3.layerjet.com
Pin-Priority: 1000

You shouldnt have to do this when replacing the official distro packages but as noted, now that official packages might get upstream upgrades, Maria should find a way to identify the packages as having an higher version number (the corresponding documentation, if i am right is that one : http://www.debian.org/doc/debian-policy/ch-controlfields.html#s-f-Version).

In regard to my Percona comment, it's not about having both repositories configured at once, the scenario is different there.

The problem is if you once had the Percona repository and now have the Percona's libmysqlclient installed, you can't install MariaDB even if you remove Percona repository: wording of the error upon installation is too vague, actually the Percona's libmysqlclient is already there, and MariaDB currently doesn't replace it.

See here for the patch proposal.
http://lists.askmonty.org/pipermail/commits/2013-February/004258.html

BTW possible workaround is using aptitude. It always offers different solutions for a given conflict, including the desired one.

I doubt that. We've had a reported issue with aptitude: MDEV-4079
The workaround was the same as with apt, using an explicit version for libmysqlclient.

But aptitude has worked for me quite well.
That reported issue complains about 'aptitude -y'.
Started with that '-y' key it works just like 'apt-get' and doesn't look for any different solutions.

I've pushed a partial fix for this. Hopefully it will be enough.

I changed the version to eg. 5.5.30+maria-1~wheezy. This will be considered
higher by apt than 5.5.30+dfsg-XXX.

This will work as long as we release new 5.5.Y versions before the
corresponding MySQL release hits the Debian repo.