Eu sei que isso é antigo, mas a pesquisa do google por esse problema aponta aqui. Então aqui está a resposta:
Debian e Ubuntu limitam o acesso a pastas. Você deve usar a pasta phpmyadmin para isso.
No Ubuntu é "/etc/phpmyadmin/" (sem as aspas).
Então a configuração seria:
$cfg['UploadDir'] = '/etc/phpmyadmin/';
