sin saber que error te da no te puedo ayudar mucho, deberias ponerlo
pero de todos modos estas haciendo la query mal, es mejor si lo haces asi (con mysqli):
Código PHP:
$mysqli = new mysqli('localhost', 'root', '', 'recados');
$query = $mysqli->prepare("INSERT INTO recados.recados (fecha, hora, Nombre, Mensaje, Telefono) VALUES ( CURDATE(), CURTIME(),?,?,?)");
$query->bind_param('sss', $_POST['Nombre'], $_POST['Mensaje'], $_POST['Telefono']);
$query->execute();
$query->close();
$mysqli->close();
es mas seguro y es OO
EDIT: releyendome tu post, si te guarda solo hora y fecha deberias comprobar que el formulario tiene method="POST"