You may have missed a step in the mod_perl install (did you do a 'make install' for both apache and mod_perl?), or you may have multiple apache servers on your system and this is the wrong one. You might also have compiled perl with a different compiler from the one you used for mod_perl. Finally, I suggest using a statically linked mod_perl because it seems to avoid a lot of possible traps.
Comment on Re: Apache::MP3 Can't locate object method "new"
Looks like perl was compiled with a different compiler perhaps. I re-installed perl and then proceeded with the same install of Apache/mod_perl/Apache::MP3 (same install procedure as yesterday). Works like a charm now.