Codice PHP:
$tabelle = mysql_list_tables('tuo_db');
while ($row = mysql_fetch_row($tabelle) ){
$nuovo = preg_replace("#^nuke_#",'nuovo_',$row[0]);
$query_agg = mysql_query("ALTER TABLE $row[0] rename $nuovo") or die(mysql_error() );
} 
Con mysql 5 potresti farlo direttamente tramite sql.