Non credo che con HAVING si risolvano le ambiguità degli attributi che non sono in MAX e GROUP BY.
Se hai mysql >=4.1 prova questa:
SELECT *
FROM `news`
WHERE categoria > 56 AND data_news IN (
SELECT MAX(data_news)
FROM `news`
GROUP BY categoria
)
Problemi li puoi avere se hai date uguali.