As previously mentioned, the voice command workaround doesn't work first time every time. I've recently gotten it to work first time by saying "shuffle-all" like it's one word. Try to say it without pausing between the words. I have a pretty thick Australian accent so if it can work for me, it can work for anyone!
According to Mazda's Bluetooth Handsfree hotline, they only guarantee compatibility up to iPhone 6 (and then only if it has iOS 8). I got a reference number from the Bluetooth folks and gave that to my dealer who is working with Mazda Customer Care. Waiting to find out if they will do anything for me.
The trick for getting the voice recognition to work in the Mazda is to press the voice command, then wait until you see text on the vehicle display. At that point, you can say 'Shuffle All' and so far that seems to be working every time.