¿Estás especificando la codificación a la hora de conectarte a la base de datos?
En mi caso, uso PDO y mi cadena para MySQL siempre suele verse de esta guisa:
Código:
$pdo = new \PDO("mysql:host=XXXX;dbname=YYYY;charset=utf8", $user, $password);
La opción del header() me parece innecesaria ya que, por defecto y a no ser que hayas especificado alguna codificación como la ISO 8859-1 en alguno de tus archivos de configuración de LAMP/LEMP, deberías tener la codificación UTF-8 por defecto en cualquier stack moderno.