Erro de caracteres com PHP + MySQL

Estou fazendo um cadastro simples em um banco MySQL, utilizando as funções utf8_encode e utf8_decode na programação PHP.

$nome = utf8_encode($_POST["nome"]);

O problema é nas informações qua ele guarda nas tabelas saem com caracteres estranhos no MySQL, mas na aplicação os dados saem corretamente.

Se eu for olhar a tabela no banco pelo phpmyadmin, O nome João no banco está: José