Edit: As i now have three answers that do not answer the question: This question is not about getting the association to work again. I do not like fighting symptoms, i prefer cures.

After associating my MP3 files with MPlayer using the Open with/Choose default program... dialogue i can no longer change that association using said dialogue, the Always use this [...] Checkbox is henceforth always greyed out (Control Panel > Default Programs > Associate a file type or protocol with a program does not let me change it either, it seems to just use the same dialogue anyway).

That also happened for MP4s but not for MKVs for example, and if i associate my MP3s with other applications like VLC it does not get blocked. I would really like to know why that is and if i can avoid this beforehand (thankfully i know ways to fix it afterwards already).

Edit: Another obervation: The blocking programs (i managed to block it with an association to Visual Studio as well) do not appear in the Recommended Programs of the open-with-dialogue (And the explorer said: "The current program is not recommended, but i won't let you change it, ha!").

Edit: A screenshot as requested:

As you can see on the top left (if you know the icon of MPlayer), the file is currently associated with MPlayer.

Edit: Ways to fix it (Note: This question is not about fixing it)

1. Using the Default Programs

   Control Panel > Default Programs > Set Default Programs, select WMP, Choose defaults for this program, check .mp3

   This should reassociate the files with WMP and you can create a new association in the explorer.

2. Using the registry (As always, keep your hands off it unless you know what you are doing or if you are fine with accidentally breaking your system)

   HKEY_CURRENT_USER > Software > Microsoft > Windows > CurrentVersion > Explorer > FileExts > .mp3

   Here you could for example clean up the open-with-list, and the current default program seems to be saved here as well in the key UserChoice, there you can change the ProgId string to another application, you can associate it with WMP by entering WMP11.AssocFile.MP3 or just pick another application right away.

   You may need to mess with permissions on the key though, if you cannot change the ProgId value.