Algo asì?
Código PHP:
require_once('../vars.php');
$check_ctg = '';
$datoslinks = mysql_query("SELECT * FROM links ORDER BY categoria, id ASC");
$i=0;
while ($link = mysql_fetch_array($datoslinks))
{
if($link['categoria'] != $check_ctg && $i) echo "<p>logo</p>";
/*
* tu codigo
*/
$check_ctg = $link['categoria'];
$i++;
}