Entonces si con un solo condicional simple funciona, prueba a anidar dos condicionales simples.
Código PHP:
$sexo = $_POST['sexo'];
if($sexo !="f"){
if($sexo !="m"){
echo "No ha completado los datos";
}
else{
echo "Ha completado correctamente los datos";
}
else {
echo "Ha completado correctamente los datos";
}