I started encountering this in early- to mid-January as well. Very frustrating as we use our Echo devices to listen to our music a lot, and a lot of our library is m4a.
I detailed most of what I’ve found about it over here in this reddit thread. (I didn’t see this issue until now.)
TL;DR it seems like a bug that Amazon introduced in the Echo firmware, starting around version 828907XXXX.
