This is a big deal in China and Russia[3] where they block the service since they have no way of intercepting it (ie. it is secure enough for two very large governments to have no way of dealing with it).
Further proof is that there are no publicly known cases where skype call or chat logs have been submitted as evidence, while you see google, microsoft, ebay, craigslist etc. appear all the time.
Skype is an independent company again - and the reason why eBay bought it back then is revenue ($850M pa last year), not some conspiracy theory
outside of the odd client exploit, skype is safe. I would trust it if I was a dissident in an unfriendly foreign country and needed to communicate securely.
[1] http://www.voiptechchat.com/tech/34/skype-says-no-to-wire-ta...
[2] http://news.cnet.com/8301-13578_3-9962106-38.html - see skype only IM company that does not comply with wiretap requests
[3] http://arstechnica.com/telecom/news/2009/07/russia-not-the-f...