I had this problem bugging me for weeks and I couldn't find the answer on the forum. I finally figured out the cause and fix and hopefully it will be useful to someone else.

System: 2014 MMI

Problem: The "Random Playback" setting of SD music in MMI keeps getting un-checked every time the car is restarted.

Cause: When a DVD is inside the stereo, the system forces un-checking of random playback. Apparently this un-checking leaks to other audio sources such as the SD card.

Fix: Take the DVD out. Take the SD card out and put it back in. Check random playback in Settings again. It should stay.

Hope this helps someone.