Ok, eu tenho que trabalhar. Espero que ajude alguém colocando aqui.
Eu tive que mudar o /etc/apache2/mods-enabled/fcgid.conf para dizer a ele para usar o php5-cgi (feito quando eu fiz a pergunta):
root@srvr-test:/etc/apache2/mods-enabled# cat fcgid.conf
<IfModule mod_fcgid.c>
AddHandler fcgid-script .fcgi .php
FcgidConnectTimeout 20
# Where to look for the php.ini file?
# Maximum requests a process handles before it is terminated
MaxRequestsPerProcess 1000
# Maximum number of PHP processes
MaxProcessCount 10
# Number of seconds of idle time before a process is terminated
IPCCommTimeout 240
IdleTimeout 240
#Or use this if you use the file above
FCGIWrapper /usr/bin/php5-cgi .php
ServerLimit 500
StartServers 3
MinSpareThreads 3
MaxSpareThreads 10
ThreadsPerChild 10
MaxClients 300
MaxRequestsPerChild 1000
PHP_Fix_Pathinfo_Enable 1
</IfModule>
Então eu tive que editar o /etc/phpmyadmin/apache.conf para adicionar + ExecCGI na seção:
root@srvr-sandbox1:/etc/phpmyadmin# cat apache.conf
# phpMyAdmin default Apache configuration
Alias /phpmyadmin /usr/share/phpmyadmin
<Directory /usr/share/phpmyadmin>
Options FollowSymLinks +ExecCGI
DirectoryIndex index.php
....