I realised that it was the wrong forum only after I posted and was unable to move or delete the post.
Thanks for the help though. I will try to get the hosting company to update there MySQL server version and hope that fixes it.
Thanks again.
I am having the same issue after the feeds being fine for about 1 year but now the order is oldest first and latest last.