Search for suitable codec?
 

When launching Totem Movie Player I am met with the following "The required software to play this file is not installed. You need to install suitable codecs to play media files".

Then when I attempt to install the recommended codec the following message is received: "gstreamer0.10-Plugins-Ugly".

Now what?

Install it. You don't tell what distro you are using so we can't give more details instruction.
Just keep in mind that there is 3 plugins-pakc for gstreamer that you should install: gstreamer-plugins-good, gstreamer-plugins-bad, gstreamer-plugins-ugly. Install them all.