"packagename" can be tricky. What did you use for the "packagename" when trying to erase it? One mistake people who are new to rpm usually make is they take the package filename for the packagename, but it's not. For example, if i had this package file w32codec-1.0_20040706-10.at.i386.rpm, i'd install/upgrade it by:
rpm -Uvh w32codec-1.0_20040706-10.at.i386.rpm
(by the way, you don't want to rpm -i, do rpm -Uvh and it upgrades the package if it's already there, otherwise it just installs)
To remove:
rpm -e w32codec-1.0_20040706-10.at
Note that the package name here is the filename minus the architecture and the "rpm" extension.
If you only recall part of a package name and want to get its fullname, you can do this:
rpm -qa | grep w32
(result should be: w32codec-1.0_20040706-10.at)
For your problem, try using mplayer. It supports more formats than xine. You might want to remove the xine version that comes from Fedora web site and get the xine version posted here
http://heidelberg.freshrpms.net/. Due to legal reasons, Fedora can't add support for many formats.