It's not the MP3s, and it's only partly the WDTV. It's mostly your AVR taking too long to sync to the digital bitstream.
I've tried this on two separate WDTV Lives and one WDTV Live+.
On my HDMI Pioneer, it takes a split second for the thing to switch modes if I leave it in AUTO. That's because the receiver has to first determine WHAT the bitstream is and then switch to the proper surround mode.
The WDTV could improve on this if, when it's in MUSIC mode, if it were to "Freewheel" and send idle bits so the AVR knew ahead of time what's about to come before the actual data arrives.
My pioneer loses about 2/10 of a second of the beginning of songs. I tested this using an MP3 that I created in a digital audio editor. When I'm using analog outputs, there's NO delay.
If yours loses seconds, then it's obvious that it's an AVR issue. And I don't want my WDTV freewheeling for multiple SECONDS before music starts to accomodate slow receivers.