Debian – Cannot upgrade theSql on a Debian 6 server using apt-get

I run a Debian 6 server and use it to host a dozen of LAMP based websites.
I configured it to email me whenever a software update becomes available, and this morning I received the notification for 6 new available updates all related to mySql:

mysql-server, mysql-client, mysql-common

and few other dependencies.
I tried to run an

apt-get update
apt-get upgrade

and everything went ok until the upgrade process met mysql-client.
The error that I get is the following:

Reading package lists... Done
Building dependency tree       
Reading state information... Done
Correcting dependencies... Done
The following packages will be upgraded:
   mysql-client-5.5
1 upgraded, 0 newly installed, 0 to remove and 0 not upgraded.
1 not fully installed or removed.
Need to get 0 B/1,772 kB of archives.
After this operation, 7,049 kB of additional disk space will be used.
Do you want to continue [Y/n]? Y

Reading changelogs... Done

(Reading database ... 84121 files and directories currently installed.)
Preparing to replace mysql-client-5.5 5.5.38-1~dotdeb.0 (using .../mysql-client-5.5_5.5.46-0+deb6u1_amd64.deb) ...

Unpacking replacement mysql-client-5.5 ...
dpkg: error processing /var/cache/apt/archives/mysql-client-5.5_5.5.46-0+deb6u1_amd64.deb (--unpack):

 trying to overwrite '/usr/share/man/man1/mysql.1.gz', which is also in package mysql-client-core-5.5 5.5.38-1~dotdeb.0
configured to not write apport reports
                                  dpkg-deb: subprocess paste killed by signal (Broken pipe)

Processing triggers for man-db ...

Errors were encountered while processing:

 /var/cache/apt/archives/mysql-client-5.5_5.5.46-0+deb6u1_amd64.deb
E: Sub-process /usr/bin/dpkg returned an error code (1)

I'm not experienced enough to completely understand what happened. I tried to run the apt-get -f install as suggested by the message, but nothing happened.
I also tried to remove mysql-client (the idea was "I remove this one, then re-install it from scratch") but also this operation failed with the same error.
I tried to purge mysql, but the system was unable to complete that operation either.

At the moment, I re-started the service, and everything looks to be working now, but the problem with this failed upgrade persists.

Here is a grep of all the mysql-related packages I have installed on my server:

~# dpkg -l | grep -i mysql
ii  libdbd-mysql-perl                     4.016-1                      Perl5 database interface to the MySQL database
ii  libmysqlclient16                      5.1.73-1+deb6u1              MySQL     database client library
ii  mysql-client                          5.5.46-0+deb6u1              MySQL database client (metapackage depending on the latest version)
ii  mysql-client-5.5                      5.5.38-1~dotdeb.0            MySQL database client binaries
ii  mysql-client-core-5.5                 5.5.38-1~dotdeb.0            MySQL database core client binaries
ii  mysql-common                          5.5.38-1~dotdeb.0            MySQL database common files, e.g. /etc/mysql/my.cnf
ii  mysql-common-5.5                      5.5.46-0+deb6u1              MySQL database common files, e.g. /etc/mysql/my.cnf
ii  mysql-server                          5.5.46-0+deb6u1              MySQL database server (metapackage depending on the latest version)
rc  mysql-server-5.1                      5.1.73-1+deb6u1              MySQL database server binaries and system database setup
iU  mysql-server-5.5                      5.5.46-0+deb6u1              MySQL database server binaries and system database setup
ii  mysql-server-core-5.5                 5.5.46-0+deb6u1              MySQL database server binaries
ii  php5-mysql                            5.4.45-1~dotdeb+6.1          MySQL module for php5
rc  php5-mysqlnd                          5.4.45-1~dotdeb+6.1          MySQL module for php5 (Native Driver)
ii  phpmyadmin                            4:3.3.7-10                   MySQL web administration tool

Adding the result of the apt-get remove

~# apt-get remove mysql-server-5.5
Reading package lists... Done
Building dependency tree       
Reading state information... Done
You might want to run 'apt-get -f install' to correct these:
The following packages have unmet dependencies:
 mysql-server : Depends: mysql-server-5.1 but it is not going to be installed or
                         mysql-server-5.5 but it is not going to be installed
E: Unmet dependencies. Try 'apt-get -f install' with no packages (or specify a solution).

Can anyone help me understanding how to fix this?
Thank you in advance,
Simone