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:
audio/amarok-kde4
multimedia/phonon
multimedia/phonon-xine
multimedia/qt4-phonon
x11/kdelibs4
And, do you have any gstreamer-related ports installed? (gstreamer*, gstreamer-plugins*, qt4-phonon-gst*)?