In other words, go into synaptic, click on "settings" -> "repositories"
and when the dialog box comes up, click on the "software sources" tab
and enable "3rd party software" - which will then allow you to search
for and install the "ubuntu restricted packages.

But the behavior sounds completely pathological - I've never seen a
linux system fail to play music files - if the codecs were missing, it
would give me an error about the missing codecs, I'd install them, and
then we'd be good to go.

If this is 9.04, there are some well known performance problems so I'd
advise either go back one release to 8.10, or forward one release to 9.10