Pour les autres :
sudo apt-get install php-gettext
pourrait être la réponse (surtout avec php7 car il semble que cela ne soit pas inclus par défaut, peut-être parce que c'est une extension poire).
Pour moi, la solution suivante a résolu le problème :
Dans le fichier de configuration de mon site Web, j'ai la section suivante :
<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>
Le seul changement que j'ai apporté depuis l'installation d'Ubuntu 13.04 est d'inclure /usr/share/php/php-gettext/ dans open_basedir, et cela a fait l'affaire.
Si votre open_basedir contient /usr/share/php/php-gettext/ déjà (comme dans mon cas) et vous ne pouvez pas le faire fonctionner avec les réponses précédentes, alors faites :
sudo rm /usr/share/phpmyadmin/libraries/php-gettext/*
supprime les liens symboliques
sudo ln /usr/share/php/php-gettext/* /usr/share/phpmyadmin/libraries/php-gettext
crée des liens physiques
Cela permet à phpmyadmin de fonctionner à nouveau. Pourquoi il s'est cassé en 13.04 et les liens symboliques ne sont pas suivis alors que apache.conf dit qu'ils devraient, reste un mystère pour moi.