Vamos por partes:
Supongo que 04_contacto_02.php será el código que expones primero .. No sé que o a qué pertenece el 2° bloque de código que indicas .. Por favor, no pongas código fuera de contexto o indica textualmente a que "scripts" (nombre) pertenecen para que no nos confundamos!.
** Haces un echo a $msg para ver que obtienes?
** Por qué no indicas una dirección de e-mail en:
Código PHP:
$mailheaders = "From: Tiene nuevos contactos <> \n";
algo tipo:
** Que versión de PHP usas? .. no sea que uses una versión 4.0.x nomeacuerdo o inferior donde no existían los arrays superglobales $_POST y afines ...
Un saludo,
PD: Uní ambos temas .. usé el botón "PHP" para que quede el código más "legible" como ahora veras.