I created a Squeeze VM and tried to install mariadb-server from the same repo, it worked all right for me both as a clean installation and as a replacement for MySQL 5.5.29; so at least it's not a generic problem, there must be some remains of a previous configuration on the machine where you are getting the error.

Could you please run

dpkg -l | grep -i mysql
dpkg -l | grep -i maria
dpkg -l | grep -i percona

and provide the output?
Thanks.

Here it goes -

1. dpkg -l | grep -i percona
2. dpkg -l | grep -i maria
   ii libmariadbclient18 5.5.29-mariadb1~squeeze MariaDB database client library
   ii libmysqlclient18 5.5.29-mariadb1~squeeze Virtual package to satisfy external depends
   rc mariadb-client-5.5 5.5.29-mariadb1~squeeze MariaDB database client binaries
   ii mariadb-common 5.5.29-mariadb1~squeeze MariaDB database common files (e.g. /etc/mysql/conf.d/mariadb.cnf)
   rc mariadb-server-5.5 5.5.29-mariadb1~squeeze MariaDB database server binaries
   ii mysql-common 5.5.29-mariadb1~squeeze MariaDB database common files (e.g. /etc/mysql/my.cnf)
3. dpkg -l | grep -i mysql
   ii libdbd-mysql-perl 4.016-1 Perl5 database interface to the MySQL database
   ii libmysqlclient16 5.1.66-0+squeeze1 MySQL database client library
   ii libmysqlclient18 5.5.29-mariadb1~squeeze Virtual package to satisfy external depends
   ii mariadb-common 5.5.29-mariadb1~squeeze MariaDB database common files (e.g. /etc/mysql/conf.d/mariadb.cnf)
   ii mysql-client-5.1 5.1.66-0+squeeze1 MySQL database client binaries
   ii mysql-common 5.5.29-mariadb1~squeeze MariaDB database common files (e.g. /etc/mysql/my.cnf)
   ii mysql-server-5.1 5.1.66-0+squeeze1 MySQL database server binaries and system database setup
   ii mysql-server-core-5.1 5.1.66-0+squeeze1 MySQL database server binaries
   ii php5-mysql 5.3.3-7+squeeze14 MySQL module for php5

Please note I'm upgrading from 5.1.66 not 5.5, which worked for me on Gentoo with no problem. Though I can try some other path if that's major problem on binary distro.

Okay, it does make a difference. Normally it shouldn't happen (I checked, it doesn't), but you can get it for example if you have something in your 5.1 /etc/mysql/my.cnf file that 5.5 doesn't recognize. It happens, some variables get removed between major versions, or their value sets change.

I emulated the problem by adding character-set-server = unknown to [mysqld] section of /etc/mysql/my.cnf before installing mariadb-server, and got the exact same problem:

Setting up mariadb-server-5.5 (5.5.29-mariadb1~squeeze) ...
Installing new version of config file /etc/mysql/debian-start ...
Installing new version of config file /etc/init.d/mysql ...
Stopping MariaDB database server: mysqld.
dpkg: error processing mariadb-server-5.5 (--configure):
subprocess installed post-installation script returned error exit status 1
configured to not write apport reports
dpkg: dependency problems prevent configuration of mariadb-server:
mariadb-server depends on mariadb-server-5.5; however:
Package mariadb-server-5.5 is not configured yet.
dpkg: error processing mariadb-server (--configure):
dependency problems - leaving unconfigured
configured to not write apport reports
Processing triggers for menu ...
Errors were encountered while processing:
mariadb-server-5.5
mariadb-server
E: Sub-process /usr/bin/dpkg returned an error code (1)

If you have a similar case, you'll see quite verbose explanation of the error in your syslog file. In my case it looks this way:

Feb 2 11:18:17 squeeze-64 /etc/init.d/mysql[19850]:
Feb 2 11:24:19 squeeze-64 mysqld_safe[20442]: #007/usr/sbin/mysqld: Character set 'unknown' is not a compiled character set and is not specified in the '/usr/share/mysql/charsets/Index.xml' file
Feb 2 11:24:19 squeeze-64 mysqld_safe[20442]: 130202 11:24:19 [ERROR] Aborting
Feb 2 11:24:19 squeeze-64 mysqld_safe[20442]:
Feb 2 11:24:19 squeeze-64 mysqld_safe[20442]: 130202 11:24:19 [Note] /usr/sbin/mysqld: Shutdown complete
Feb 2 11:24:19 squeeze-64 mysqld_safe[20442]:
Feb 2 11:24:19 squeeze-64 mysqld_safe[20442]:
Feb 2 11:24:19 squeeze-64 mysqld_safe[20442]: Installation of system tables failed! Examine the logs in
Feb 2 11:24:19 squeeze-64 mysqld_safe[20442]: /var/lib/mysql for more information.
Feb 2 11:24:19 squeeze-64 mysqld_safe[20442]:
Feb 2 11:24:19 squeeze-64 mysqld_safe[20442]: The problem could be conflicting information in an external
Feb 2 11:24:19 squeeze-64 mysqld_safe[20442]: my.cnf files. You can ignore these by doing:
Feb 2 11:24:19 squeeze-64 mysqld_safe[20442]:
Feb 2 11:24:19 squeeze-64 mysqld_safe[20442]: shell> /scripts/mysql_install_db --defaults-file=~/.my.cnf
Feb 2 11:24:19 squeeze-64 mysqld_safe[20442]:
Feb 2 11:24:19 squeeze-64 mysqld_safe[20442]: You can also try to start the mysqld daemon with:
Feb 2 11:24:19 squeeze-64 mysqld_safe[20442]:

etc.

Could you please check yours?

Indeed after commenting these two lines upgrade went well.

default-character-set=utf8
character-set-server=utf8

thanks for all your time on this.

cheers

character-set-server=utf8 should be fine, but default-character-set was indeed deprecated in 5.0 and removed in 5.5: http://dev.mysql.com/doc/refman/5.0/en/server-options.html#option_mysqld_default-character-set

I'm glad it works now.