Puedes hacer que no se escriba directamente la letra "ñ" sino que la reemplace con su codigo html mediante php, mira:
Código PHP:
$mensaje = $_POST['mensaje'];
$mensaje = str_replace("ñ","ñ", $mensaje);
// Y luego el codigo php de mysql_connect etc...
Asi cuando consultes los datos de la base de datos a una pagina aparezca ese codigo y se transforme a una ñ directamente.
Saludos.