Você está usando o Ubuntu 14.04 (confiável) e adicionou repositório para o Ubuntu 12.04 (preciso)?
deb http://ftp.osuosl.org/pub/mariadb/repo/5.5/ubuntu precise main
deb-src http://ftp.osuosl.org/pub/mariadb/repo/5.5/ubuntu precise main
Se eu executo a pesquisa por mariadb em packages.ubuntu.com, há mariadb já nos repositórios confiáveis do universo - veja isto link .
Você pode remover o repositório link em /etc/apt/sources.list e verificar se existem alguns repositórios estranhos em /etc/apt/sources.list.d. ?
Depois disso purgue a instalação do mariadb anterior e tente instalá-lo com
sudo apt-get update
sudo apt-get install mariadb-server
Isso instalará o maria db 5.5. Se você precisar da versão 10.1, tente com as instruções oficiais aqui .