From a fedoraforum.org post, try running:
The yum-complete-transaction man page states that it may be needed to run the program several times. Maybe the --cleanup-only will not try to complete all the transactions, removing some changes.
You may have stale pid files in /var/run. Try deleting them just before rebooting.
Also look in /var/lib/yum/ and see if you can glean any information from the transaction-all* and transaction-done* files. I'm not using Fedora now, and so I don't know if these are text files. If you know the name of a package that wasn't fully updated, try forcing a new update on the same package.
For the mp3 question, add the rpmfusion repository, for media program versions built with mp3 support.