I did.
I backed up to iCloud and iTunes last night. I then restored from iCloud and had the missing data still.
I then restored the 14th November iCloud backup (the one apple guy told me to restore), and still no data.
So I tried the 13th November (no data), before restoring last night's iTunes backup (which still has no data).
Unless by "brand new", you mean delete my existing iCloud backups for this device, then no, I'm not trying that because then I'll still have no data when it doesn't work..
OK, then yeah you did exactly what I did. I didn't delete any of my old backups, just made a new one to test with.
That's really frustrating that no one at Apple can make sense of this. I have iCloud backups turned on again for the first time in over a month, but I'm still going to make periodic iTunes backups. I just don't trust iCloud completely anymore.