Per gli altri:
sudo apt-get install php-gettext
potrebbe essere la risposta (soprattutto con php7 in quanto sembra che questo non sia incluso di default, forse perché è un'estensione a forma di pera).
Per me la seguente soluzione ha risolto il problema:
Nel file conf del mio sito web, ho la seguente sezione:
<IfModule mod_php5.c>
AddType application/x-httpd-php .php
php_flag magic_quotes_gpc Off
php_flag track_vars On
php_flag register_globals Off
php_admin_flag allow_url_fopen Off
php_value include_path .
php_admin_value upload_tmp_dir /var/lib/phpmyadmin/tmp
php_admin_value open_basedir /usr/share/phpmyadmin/:/etc/phpmyadmin/:/var/lib/phpmyadmin/:/usr/share/php/php-gettext/
</IfModule>
L'unica modifica che ho apportato dall'installazione di Ubuntu 13.04 è includere /usr/share/php/php-gettext/ in open_basedir, e questo ha funzionato.
Se il tuo open_basedir contiene /usr/share/php/php-gettext/ già (come nel mio caso) e non riesci a farlo funzionare con le risposte precedenti, allora fai:
sudo rm /usr/share/phpmyadmin/libraries/php-gettext/*
rimuove i link simbolici
sudo ln /usr/share/php/php-gettext/* /usr/share/phpmyadmin/libraries/php-gettext
crea hard link
Questo fa funzionare di nuovo phpmyadmin. Il motivo per cui si è rotto nella 13.04 e i collegamenti simbolici non vengono seguiti mentre apache.conf dice che dovrebbero, rimane un mistero per me.