Una consulta... el campo Mensaje_Id es autoincrement???? por que si es asi no deberias de colocarlo en el insert.... deberias dejarlo asip....
Código PHP:
$consulta = "INSERT INTO `Mensajes` (`Mensajes_nombre`, `Mensajes_texto`, `Mensajes_pais`, `Mensajes_fecha`) VALUES ('$Nombre', '$Mensaje', '$Pais', '$Today')";
espero te funcione...