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.