About the MP3 format, you can have endless discussions about it, but that is not appropriate in this thread. I mostly agree with you btw, but the fact remains that some of the most popular Linux distributions don't play MP3 out of the box
Alright then, but few people have an out of the box linux. I suspect that 90% of users will have installed MP3 software because they want to use it. Yes, people want non-free stuff: They want youtube (flash is not free software), they want DVDs (ooh, non-free encryption), they want to play AAC files from their iPod, etc. Ubuntu tries to be free of patent issues, which is fine. But users mostly don't care about it, so MP3 isn't much of a problem and my package would install properly for most people. But as you say, this discussion could go on forever, there's not much point here.
OGG Vorbis support will get in eventually. If more people share your opinion, maybe MP3 could be made an optional part, but I'm unsure how to present this though. It could be separated in a base package with OGG/WAV and an add-on package with MP3 support. But having a like 2KB add-on packages seems a bit ridiculous. I could also present two separated version: skype-call-recorder-without-mp3 and skype-call-recorder-with-mp3 that are mutually exclusive. RPM packages also allow subpackages, but I haven't seen support for something like this in DEB files. I'll have to check how Ubuntu/Debian handles this in other situations.
btw, support for FLAC was once on the todo list too, but I decided this is more than pointless. Skype calls aren't of a quality that deserves lossless storage. And if you really want it, or if you really want to use any other format, you can always record to WAV files and convert manually later to whatever you like.
Another option would be to include the lame MP3 encoder in your app, if its licence allows redistribution (and I think it does), but then do provide a warning that installing your program might be illegal in some countries.
Yes, but that undoes the purpose of having shared libraries, which I think is a good thing. It's also better for security and bugs. If liblame needs to be updated for some reason, Ubuntu's update feature do that and Skype Call Recorder will then also use it.
Its just my thinking that both SMS sending and Call recording should have been in Skype for Linux in the first place
I strongly agree with this! Unfortunately Skype isn't open source, so I couldn't add built-in support.

so having one program that turns Skype into what it ought to be does make sense to me.
Mmh, yes this somewhat makes sense, but it's going to be one huge bloaty program... if someone wants to take that path, why not, but I don't really want that for myself.
The other extreme would be that Skype would consist of 245 programs, one for chat, one for voice, one for SMS, one for video (which used to be seperate as you might remember), etc.
You can group them in a sensible way; video and audio belong together, they are both part of the 'call' that is recorded. This allows people to install just what they want, instead of installing one huge complex application when they in fact only want to record one call.
Well, I have all the dependencies installed on my machine now, so that wouldn't be a very good test case. But I'll try with a more fresh/naked Ubuntu install later this week, and let you know.
That would be nice, but don't bother too much either. In case it wasn't already obvious, with the binary package you can now uninstall cmake, g++ and the -dev packages, unless of course you plan to continue to compile from source or use the packages in other ways.
I forgot to ask, did desktop integration work for you? You get a menu entry with an icon?