There's kind of a big problem though: you need two computers to do this. One to make the Skype call and the other to record the interview, routing the audio from one to the other. Ethan Zuckerman, who has experimented with Skype recording, says this is because Skype seizes all of your computer's sound card when you use it, and recording programs like Audacity do the same thing, so you can't use both simultaneously. This is a huge pain. I don't have 2 computers myself. I suspect most people don't. Kind of puts a damper on Skype's potential to become a grassroots media production tool, if you ask me.
I wish Skype would come up with an app that lets you record your conversations on the same computer. Or alternatively, I hope somebody else comes up with a Skype-like service that makes it possible to record conversations.