Experienced the same problem.
For some reasons, the '/usr/share/services/audiocd.protocol' has disappeared from FC4's 'kdemultimedia-3.5.0-0.1.fc4.i386' RPM (updates-released section).
(Well, some report an interoperability problem between KDE 3.5 and cdparanoia... but is it a reason to make things disappear like this ?!? Lost 3 hours today working on that case)
Thank you so much...
I (temporarly) solved the problem by manually downloading and installing the 'kdemultimedia' packages (and dependencies) from 'kde-redhat.org':
rpm -Uvh kdemultimedia-3.5.0-4.fc4.kde.i386.rpm kdemultimedia-extras-3.5.0-4.fc4.kde.i386.rpm akode-2.0-0.4.rc1.fc4.i386.rpm
' Hope this helps