Try browsing to \Program Files\StreetDeck and running the SDConfig executable (or something like that) to edit the Application Data Path as opposed to using the Start->Programs->StreetDeck->Tools->Edit Media Paths (or whatever it's called).
Edit the last field for the default Application Path to the new default, save, and then try to set the media pathI(s). I had a similar problem when I tried to change the defaults/saved paths.
They wouldn't save and I had a start error that the default skin directory couldn't be found after upgrading to 220.127.116.11 then patching to .4. Once I changed it over to the new default of C:\Documents and Settings\Administrator\My Documents\StreetDeck, I could then edit and save changes from the default\old media paths.
Even edits to the mediapaths.dat text file were ignored. SD apparently embeds the application data path and parses that on startup and the utility likely does as well. It's possible the utility just keeps referring back down the old path while saving your edits. They're being save but just in the wrong place?
There's something of a readme about this in the .2 update post that the default application path has changed from ..\..\Local Settings\Application Settings to "My Documents".