I feel your pain. I did the trade in process for my phone, but kept hold of it whilst trying to sort this out. I posted it to them yesterday but had an email saying it if wasn't returned in 14 days (from when the returns pack was delivered) then they couldn't guarantee the price...I think tomorrow is 14 days, but there's a postal strike today and tomorrow!My music etc is all saved to iCloud. I don’t have my old phone now as it’s been wiped & sold on. Currently chatting to apple but just getting the same responses, reset etc. all of which I’ve done & to no avail. Ridiculous really.
You shouldn't need your old phone. I had thought about un-syncing the media from my old phone and then backing that up and using that "new" backup...but would've lost messages received in between, so didnt do that.
If your music sync's from icloud then that probably isnt the issue. I suspect my music might have been an issue as I had manually synced it all onto the phone, not just download when played for 1st time.
What about tv shows/movies? Do you have any of those? A previous poster said they manually downloaded all videos etc (and then deleted those they didnt want on the phone) which cured it. You don't need to reset the phone to do that, but you'll need to be on wifi.
I think Apple support don't know what is going on, hence unable to give direct responses.