Hrm, how bizarre.
I installed Amarok 2.0 (upgraded to 2.1 recently) on my KDE 4.x box (originally 4.1, then 4.2, now 4.3) and could play MP3 files from the get go, through all the in-place upgrades.
What version of the following do you have installed:
And, do you have any gstreamer-related ports installed? (gstreamer*, gstreamer-plugins*, qt4-phonon-gst*)?