If you get an error along the lines of DecoderMAD: failed to open input, the chances are very good that the audio path is set incorrectly in the MythMusic config.
Keep in mind that just because you can see your songs in the list doesn't mean that your audio path is correct (odd, but true nonetheless). This has actually happened to me twice in the past and on both occasions I could see all the files, but the actual path was pointing elsewhere. As soon as I set the path to the actual audio file location the DecoderMAD issue was solved.
To check your path, choose Utilities/Setup → Setup → Media Settings → Music Settings → General Settings. Now double, and then triple, check the path leading to your mp3s (or ogg, or flac or whatever audio format you're using). If the path is off, fix it. You will also want to run Utilities/Setup → Setup → Music Tools → Scan for New Music after you do this.
Next, save your settings and give MythMusic a try again. Chances are, your DecoderMAD: failed to open input issue will be solved.