"All Photos" album order mixed up after restore (device change)

I recently had to back up and restore an iPhone 6 to a new iPhone 6.

I did a full backup to iTunes, then restored to the new iPhone 6 from that backup.

Everything was restored, including all photos... (I have iCloud Photo Library turned on)... EXCEPT in the "All Photos" default album on my phone, the photos are not in the usual date order. They are all mixed up, mostly in large consecutive chunks, but with some individual photos randomly dispersed. No pattern that I can see otherwise. It looks like: (Jan-Mar 2010)--(Apr 2013-Nov 2013)--(Apr-2010-Feb 2013)--(Dec 2013-Feb 2014)--(Apr 2014-Sep 2014)--(Feb 2015 to today). Something like that.

The "Photos" tab, where you see collections, years, etc, is in date order. On iCloud.com, it is in the right order in the "All Photos" album. However, it is in the *wrong* order on my iPad, where I also have iCloud Photo Library turned on.

What I have tried:

1) Turning off, then turning back on iCloud Photo Library beta.

2) Full erase and restore from iCloud

3) Full erase and restore from a new backup

One more option would be to try restoring from the backup I made before the new iPhone 6, but then I would lose changes since then (about 2 weeks), and I would rather try to avoid that.

Has anyone seen this before? Why is this happening, and what else can I try to fix the order? I saw another thread about out of order events, but this seems different.