La solución que te han dado es la mejor sin lugar a dudas, no obstante cuando tenemos ya salida html y queremos redirigir a otra página, lo único que nos queda es echar mano de JavaScript.
Código PHP:
$idcon = mysql_pconnect($Servidor, $Usuario, $Clave);
if ($idcon == 0) {
// Antes -> header('location: mipagina.php');
?><script>location.href='mipagina.php';</script><?
}