Yup, Xbox Music: The Metadata Apocalypse (the only part of this debacle I enjoy is writing that phrase).
One other thing I'd add to the comments above is make sure you find the metadata and connect to Xbox options on all your devices, see if you can get stable metadata and then turn things back on from there if you want to. I kept having problems across all five devices, turns out I hadn't clicked off the metadata setting on two of them - ones I don't use much. When I turned those off as well, my phone seemed to start to stabilize.