Me parece raro que no te funciona, la mejor manera de saber si tu consulta esta fallando es mostrarla, copiarla y ejecutarla directo en mysql:
Código PHP:
<?
$ssql = "select count(*) AS TotalReg, DATE_FORMAT(Fecha_Publicacion, '%d/%m/%Y') as publicado from avisos " . $criterio . " ORDER BY Fecha_Publicacion DESC";
con que version de mysql estas, porque no copias un par de lineas arriba y aba jo de tu problema y copias el error completo, se me hace mas problema de sintaxis en tu codigo php, cya