Você deve tentar instalar o php do ondrej repo
sudo add-apt-repository -y ppa:ondrej/php
sudo apt-get update
sudo apt-get upgrade
sudo apt-get install php5.6
Senão use aptitude
para instalar qualquer dependência ausente automaticamente
instale-o via sudo apt-get install aptitude
e depois sudo aptitude phpmyadmin
, então ele mostrará os conflitos que existem e as opções para corrigi-los