Antes del header no puede haber ningun 
echo 
es decir, haz tu funcion if/else inversamente  
Código:
 <?php
$conexion=mysql_connect("localhost","root","password") 
  or  die("Problemas en la conexion");
mysql_select_db("midb",$conexion) 
  or  die("Problemas en la selección de la base de datos");
$registros=mysql_query("select usuario,password,nombrecompleto
                       from autenticacion where usuario='$_REQUEST[usuario]' and password='$_REQUEST[password]'",$conexion) or
  die("Problemas en el select:".mysql_error());
if (!($reg=mysql_fetch_array($registros)))
{
  header("Location: htt....");
  }
else
{
    echo "<fieldset>";
    echo "<b>";
    echo "Bienvenido:";
echo "</b>";
    echo "<br><br>";
  echo "".$reg['nombrecompleto']."<br>";
echo "</fieldset>";
}
mysql_close($conexion);
?>