Definitivamente es un problema de optimización, porque en cada iteración en el while de $registro = mysql_fetch_assoc($rf) lees toda una tabla y recorres los registros para ver si cumplen condiciones, eso deberías hacerlo desde la consulta:
Código PHP:
Ver originalinclude("../conexionesBD/conexion.php");
$rs = mysql_query("SELECT * FROM actaf WHERE nmatricula = 0"); // El siguiente if no es necesario, si no hay resultados no entrará al while
// if (mysql_num_rows($rs)>0){
// En esta consulta necesitas un filtro
// WHERE numidprop = $registro['cedula'] and estmatricula... bla bla bla
$rf = mysql_query("SELECT * FROM sii_11.mreg_est_matriculados");
// El siguiente if no es necesario
// if($registro["cedula"] == $fila["numidprop"] and $fila["estmatricula"] = "MA" and $fila["fecmatricula"] >= "2012/08/01"){
$q="UPDATE actaf SET
nmatricula = '".$fila['matricula']."',
fecha = '".$fila['fecmatricula']."'
WHERE cedula = '".$fila['numidprop']."'
";
// } // cierre de if no necesario
} // fin while fila
} // fin while registro
// } cierre de primer if no necesario