Los navegadores ordenan en base al nodo pubDate, que deberás agregar a tu xml en el mismo formato que el nodo espera:
Código PHP:
<pubDate>Sat, 11 Apr 2009 00:00:00 +0000</pubDate>
Seguramente podrás aplicar una transformación de manera sencilla con alguna función de tu base de datos o el lenguaje de servidor que uses, para que tu fecha tenga el formato adecuado.