I'll be down-voted, although I solved the problem with: .. FaceTime. If you don't have a mac you can get a ipod touch. That's what I use to talk with my family USA->Italy. Is the only thing I found that is reliable and has a quite good quality.
What makes FaceTime incredible is that no one else on the planet can make anything even close to adequate in that space.
It can be mind boggling to cycle through Skype, Lync, Google Hangouts, and every other piece of chat software on your computer, all failing in bizarre ways, only to think, "Oh yeah. Let's try FaceTime" and have it work.
So, perhaps Skype and GV are suffering from over-extended networks? It must be hard to justify investing in better network infrastructure for a free product (or when your revenues are minimal). On that note, I don't get the impression that BlackBerry's network has much of a problem with network load these days...
Facetime is what makes it possible for me to stay in touch with my family on the other side of the planet, and that's even if I'm sitting out in a park far from Wifi. It just works, and even if it hiccups once in a while, the reliability is high enough that you just shrug it off with the confidence that it will recover. This is on LTE with good reception.