I just spent an evening debugging the girlfriend's laptop as it somehow flat-out rejected to play video in Totem (ever since upgrading her xubuntu install from 8.04 to 8.10). Totem has a convenient browser plugin for Firefox, so this is kind of a problem if I don't want her booting to windows just to see some streaming video of TV series reruns. Thankfully, just before giving up, I found this Ubuntu bugreport talking about the same issue. Turned out, you just need to install a bunch of gvfs packages (virtual file system stuff, providing GIO, which Totem needs to look up both the url and the codecs it turned out). I installed:

• gvfs
• gvfs-backends
• gvfs-bin
• gvfs-fuse
• libgvfscommon0

... and everything was back to normal again. Stupid !@#$ :)