First question is do you have the codecs installed. If you do, then it's probably a matter that totem can't find them. That can be fixed by either moving them to where totem expects them, creating a symlink, or changing configuration. Changing configuration settings are probably going to be applicable to what back-end you're running.
I used to use totem and was able to get it to work with those formats. So I think it's probably just a matter that totem can't find them when it needs to. However, I do remember that I would sometimes run acrossed videos that totem would complain about and not be able to run in spite. For instance, I could usually play a .wmv, .asf, .avi, etc, but sometimes I would run into one that wouldn't. I usually just chalked it up to that they may have been a version of the format that totem either didn't like, or that the video files were messed up to begin with.
This link may help you if you're running totem as a front end to xine. It did in my case.
I believe that totem is really just a front-end. So what you'll have to do to fix will probably apply to what back-end your totem is running. The above link applies to totem running over xine. You can check what back end your totem is using by clicking on help: about.
Good luck, I like totem too. I think it's one of the better ones that I have tried. I hate how most of the other players use skins. I really think skins are the dumbest concept there ever was. But that's just my opinion. The only thing I don't like about totem is all of it's dependencies on gnome components. Unfortunately, if you have a lower-end system, you get stuck with that extra overhead in order to use totem. If I had a more modern system to work with, I probably would be running gnome since it's got some nice applications and there is always lots of new ones being developed for it.
Of course Kaffeine is another option for a front-end, but I think you stick with the one you like.