So does this mean XMMS gets relegated to non-free now?
No. Putting it there would violate Frauenhofer's rights under just about any country's laws. You don't find Adobe Photoshop in non-free, do you?
The software in non-free is still free-as-in-beer. It's just not free-as-in-speech, at least under DFSG rules.
XMMS (or any other MP3 player), under Frauenhofer's new rules, cannot be free in any sense of the word. Unless some wealthy benefactor is willing to donate $60k to XMMS to pay off Frauenhofer.
By the way, since patent-holders can play "submarine" games -- not revealing or selectively enforcing their patents until a technology is widely adopted -- no software can really be guaranteed to be free in either sense.