I guess I'll just keep updating this thread with CX5 woes and Windows Phone. This morning no amount of shuffle requests could coax Cortana into actually shuffling my audio over Bluetooth. I still blame Mazda for these issues, but no proof so far. It looks like after using a fresh WP install for a while shuffle breaks. This happened with my 8.0 install as well: it worked for a bit, and afterward I was never able to get it back to work.
Anyway, using voice command in the steering wheel (the little dude with the wifi signal coming from his mouth) there is an option shuffle > all. That did turn shuffle back on, but it also turned on 'scan' meaning you get 20second snippets of your song. Hoping scan turns off later, and that shuffle sticks. We'll see, I'll update if I find anything new.