Yep...you have it right. If the obvious name doesn't work for a program you can do an "apt-cache search ???" to find the right name of the package. It looks like xine can be removed by apt-get remove libxine1.

And it's a good idea to use -s (simulate) first to see what is going to be removed and such. For instance if I simulate removing libxine1 I get:

Code:
evan@knoppix:~$ sudo apt-get remove libxine1 -s
Reading Package Lists... Done
Building Dependency Tree... Done
The following extra packages will be installed:
  noatun-plugins
The following packages will be REMOVED:
  kaffeine kdemultimedia libarts1-xine libxine1 xine-ui
The following packages will be upgraded
  noatun-plugins
1 upgraded, 0 newly installed, 5 to remove and 543 not upgraded.
Remv kaffeine (0.4.2-1.1 Debian:unstable)
Remv kdemultimedia (4:3.2.2-1 Debian:unstable)
Remv libarts1-xine (4:3.2.2-1 Debian:unstable)
Inst noatun-plugins [4:3.2.1-1] (4:3.2.2-1 Debian:unstable)
Remv xine-ui (0.9.23-2 Debian:testing)
Remv libxine1 (1-rc3c-1 Debian:testing)
Conf noatun-plugins (4:3.2.2-1 Debian:unstable)
So it's going to remove KDEMultimedia. I'd have to get that reinstalled afterwards.