Se fai così, per esempio,
Codice PHP:
echo "<input type=\"checkbox\" value=\"$idcat\" name=\"scelta[]\">$namecat
"; 
quando recupererai i dati checcati, li avrai nell'array
$_POST['scelta'] e ti basterà fare un ciclo:

Codice PHP:
foreach($_POST['scelta'] as $idcat)
 {
  mysql_query("INSERT INTO galleria_perms VALUES('$idcat', '$uid')");
 } 
ciao