Problema privilegios MySQL

Pessoal,
estou com problemas de privilégios no MYSQL. No PHPMyAdmin quando clico na opção privilégios da a seguinte mensagem:
Warning: Your privilege table structure seems to be older than this MySQL version!
Please run the script mysql_fix_privilege_tables that should be included in your MySQL server distribution to solve this problem!
Executei o comando mysql_fix_privilege_tables e o mysql_fix_privilege_tables --password='minha_senha' mas da o seguinte erro:
ERROR 1045: Access denied for user: 'root@localhost' (Using password: YES)

Então atualizei o phpmyadmin através do apt-get install. Ao entrar novamente no phpmyadmin após a instalação, não encontrei mais a opção privelégios.
Abaixo da opção "Criar novo Banco de Dados" tem escrito em vermelho "Sem privilégios".
Não consigo criar um novo banco e muito menos mexer com previlégios.
Com isso ocorreu de acessar o phpmyadmin como root sem senha e mostra todos meus bancos sem informações, como se não tivesse nenhuma tabela, como se os bancos estivessem vazios.
Até assustei. Imaginei de cara que tinha perdido os dados mas sem muita preocupação, pois tenho backups. Mas o estranho que nenhum serviço meu parou, então percebi que os dados estão lá, só o phpmyadmin que não consegue exibir.
Tentei então criar uma tabela em um BD já existente. Só que não consigo, dá a seguinte mensagem:
#1142 - CREATE command denied to user: '@localhost' for table 'teste'
Nem por linha de comando via msql, sem a interface phpmyadmin, consigo vizualizar os dados ou fazer se quer qualquer alteração, inclusão ou exclusão.

O que fazer??


Valeuuuuuuuu