codice:
$flag="";
$links_all = mysql_query("SELECT * FROM links ORDER BY tipo", $db_comm) or die(mysql_error()); 
while($row=mysql_fetch_array($links_all))
{
  if($row['tipo']!=$flag)
  {
  echo"
{$row['tipo']} :
";
  $flag=$row['tipo'];
  }

echo"<a href=\"{$row['link'}\">{$row['nome']}</a>
";
}
All'inizio dello script ho impostato $flag="" solo per farti capire su quale variabile vado ad operare, cmq è superfluo se vuoi puoi eliminare la prima riga.
Dovrebbe funzionare, se vuoi te lo spiego anke.