Why can't plugins be found for my Media Players?

I don’t know what media you’re trying to play, but if you install Ubuntu Restricted Extras, it will install a lot of plug-ins that might have restricted licenses that prevent Ubuntu from installing them by default due to ideological reasons (as well as other restricted software, such as Flash, if you don’t already have it). That should install support for most formats.
(Was Ubuntu Software Center already present in Lucid? Lucid is 10.04 right? If so, installing it through there should speak for itself, I think. If not, ask for help :)

If you still have some edge cases that don’t work, you can try installing the VLC media player, which has built-in support for a lot of media formats (which is the main reason for it being really popular).