If that doesn't work, you should update your codecs by--

1) rm -fr ~/.xine # i don't think this actually matters, but it might have
2) rm -fr ~/.kde/share/apps/amarok
3) sudo vim /etc/apt/sources.list
ensure that I have this line
deb http://us.archive.ubuntu.com/ubuntu/ edgy universe multiverse
4) sudo apt-get --purge remove libxine-extracodecs
5) sudo apt-get install --reinstall libxine-extracodecs