Atualmente, existem alguns problemas de instalação conhecidos que também encontrei ontem. Os caras do MariaDB "criaram uma página para aqueles que se depararam com os erros de empacotamento presentes em 5.5.33":
MariaDB 5.5.33 Problemas de instalação do Debian e do Ubuntu
Você pode tentar alterar sua configuração de sources.list para
deb http://ftp.osuosl.org/pub/mariadb/mariadb-5.5.32/repo/ubuntu precise main
e execute um sudo apt-get update
depois disso. Em seguida, basta instalar a versão mais antiga até que consertem tudo:
sudo apt-get install mariadb-galera-server