Skype is similar to a P2P idea like Bittorrent.
When you install Skype on a home PC, it uses your broadband connection to both send and receive the packets making up your call, but also "borrows" a bit extra to help route other peoples calls across the network. (No, you can't listen to the other peoples calls!)
Because of this, many people do not like the idea of Skype, as it steals bandwidth. In addition if your internet connection is heavily loaded, your local exchanges contention ratio is poor, or the ISP you are with is actively throttling (traffic shaping) certain packets, Skype can be troublesome or call quality poor/dropping.
I have used Skype round a friends house over Demon Internet Broadband and it worked quite well. He uses it for international calling to Holland and is very happy with the service, but they are not heavy internet users. Some people swear by it, others swear at it.
The trouble with using it (Skype and its ilk) over the cellular system is several mobile phone networks really don't like the idea of you using the data plan you have paid for, for free calls, when you should be using up your voice minutes and then paying them for voice calls! I remember T-Mobile in the UK stopped VoIP use for a while, I presume they have now reactivated it (?) and there was the aggro over Orange stripping ther VoIP functionality out of the Nokia N (95? was it) and preventing VoIP calls even if the application was reintroduced to the handset.
I suspect that in the next year to eighteen months that VoIP use on mobile handsets will grow to the point that consumer demand forces the networks to play ball a bit more. Until then, you are fighting networks to avoid packet shaping or simple lack of functionality, 3G latency and possible bandwidth use acceleration for the "free" VoIP clients. It's a bit of a mess, like early MMS days, but will clear up soon.
Regards
Ivan at devicewire.