un 10 para maycolalvarez y otro para bookmaster, efectivamente el problema en un principio era que el charset debia ser declarado en el header
Cita: $header .= 'Content-type:text/plain; charset=UTF-8' . "\r\n";
y luego el otro problema era que en vez de:
Cita: mail($para, $asunto, utf8_decode($mensaje), $header);
mail($para2, $asunto, utf8_decode($mensaje), $header);
Habia que poner:
Cita: mail($para, $asunto, utf8_encode($mensaje), $header);
mail($para2, $asunto, utf8_encode($mensaje), $header);
Asi que muchisimas gracias