allora vediamo se viene al primo colpo

aggiungi :

<form name="frmtutor" enctype="multipart/form-data" method="post" action="elimina_record.php ">

cambierei anche la linea:

echo "<td class=tabval align=center><input type=checkbox name=chk_".$row['user_id']." ></td>";

poi crei la pagina elimina_record.php in cui dovresti recuperare tutte le righe selezionate con:

foreach ($_POST as $item => $valore){
if (substr($item, 0, 4) == "chk_" ){
$sql="( user_id =".$valore.") OR";
}
}

if ($sql != "") {
$sql= "DELETE FROM nome_tabella".
" WHERE " . $sql;
$sql= substr($sql, 0 ,strlen($sql)-4);

mysql_query($sql);


l'ho fatta un po al volo, provalo

}