Holy this really pissed me off
I had this issue with my old photos from my N9/N8 and dug into try and fix it.
You need to update the EXIF information of the photo cause it seems to use a flag called Create Date to order the files. Well that's the one inconsistency. Anyways, to get it all I decided to update all the pictures EXIF date informations to be the same date. It seem Date/Time Original exists everywhere but is not used by WP8 to sort so I used that date which was still good to update everydate possible in the picture exif info.
I used a command line tool called exiftool
ExifTool by Phil Harvey
and used this command to update all dates information in the EXIF
exiftool "-datetimeoriginal>Alldates" *.jpg
And now my pictures going back to Aug 2011 are properly grouped and sorted.