Para otros:
sudo apt-get install php-gettext
podría ser la respuesta (especialmente con php7, ya que parece que esto no está incluido de forma predeterminada, tal vez porque es una extensión de pera).
Para mí, la siguiente solución resolvió el problema:
En el archivo conf de mi sitio web, tengo la siguiente sección:
<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>
El único cambio que hice desde la instalación de Ubuntu 13.04 es incluir /usr/share/php/php-gettext/ en open_basedir, y eso funcionó.
Si su open_basedir contiene /usr/share/php/php-gettext/ ya (como en mi caso) y no puede hacer que funcione con las respuestas anteriores, entonces haga:
sudo rm /usr/share/phpmyadmin/libraries/php-gettext/*
elimina los enlaces simbólicos
sudo ln /usr/share/php/php-gettext/* /usr/share/phpmyadmin/libraries/php-gettext
crea enlaces duros
Esto hace que phpmyadmin funcione de nuevo. Por qué se rompió en 13.04 y los enlaces simbólicos no se siguen mientras apache.conf dice que deberían seguirse, sigue siendo un misterio para mí.