Due to Skype's ever lasting bad Linux support and various crashes, I started to look for an alternative. I do give Skype credit, they try to take a lot of effort from the user to get things running. I toyed a bit around with jingle from jabber, but with not much success, neither Pidgin nor Empathy get the communication over Jingle right. However, I was pretty often (sadly not always - but I have to admit there were some pretty tough firewalls, I tried it with) successful with Jitsi. Yes, I should have tried this earlier as I was google-mentor for sip-communicator, Jitsi's predecessor, several times. Ok, Jitsi, I am back as one of your loyal supporters.
Even with the problems with the firewalls, I mentioned before, I had a lot of success using just the SIP-protocol, not jabber/jingle ( I used a free account from iptel.org for testing). Great video and voice!
With SIP, I also could easily connect to linphone (lots of trouble with ekiga though).
So my advice for you Linux users (and others who are unhappy with Skype) is: ditch Skype (or only use it on demand), get a jabber (or googletalk - you have this already, if you use googel mail) or sip-account and start using Jitsi. If you have a very small machine (Jitsi can be sometimes a little heavy on your resources - however, if you have used Skype before - do you actually care?), I suggest using linphone with a SIP-account (harder to set-up though).
A nice plus of Jitsi is also the option to share your desktop and be remotley controlled (in contrast to Skype, where you can only show your desktop). Native OTR and ZRTP (encryption of your chats and calls -- like in Skype, but with an open protocol) support is another plus. Also multi-platform ability, making your (Windows or Mac) family memebrs use Jitsi and still being connected to them is an another additional benefit.