I was looking for a Skype recorder that works in Linux and I came across this application:
http://atdot.ch/scr
I went to downloads and tried out their RPM version, and it (almost) worked right away. There were a few awkward steps for my distro (Fedora 14) and I can't say how it performs in other distros, but it seems by and large this works well, once you've fixed any dependency problems.
For my reference, and for the good of others, here are the steps required to make this work in Fedora 14:
