Ao se deparar com o erro abaixo no seu phpMyAdmin, no Debian / Ubuntu:
Could not save recent table! #1146 - Table 'phpmyadmin.pma__recent' doesn't exist
Basta executar o comando dpkg-reconfigure phpmyadmin e pronto! O problema estará resolvido.
# dpkg-reconfigure phpmyadmin
Para a galera do Ubuntu, creio que será necessário adicionar sudo a frente do comando.