Empathy or Gajim Audio/Video Call using Jabber not working
 

I am running Linux Mint 18 (As is my son). Trying to use Empathy and/or Gajim to audio/video call both with jabber.at accounts.
we can text chat OK, but the audio & Video will not connect.
Can anyone tell me how to achieve this. I have dumped Skype, and need an alternative for Linux and Android.
Empathy - added account-plugin-salut account-plugin-jabber telepathy-salut telepathy-gabble
Gajim - added python-farstreamer and have the gstreamer bad plugins installed
We have even tried Jitsi.
Just cannot get the sound to work. Have tried autoselect, and the Pulse Audio items.
Any ideas?
Anyone got something working instead of Skype? Wire works, but like Skype uses too much bandwidth for my slow Internet connection, so have to use audio only.

First make sure your sound system is really working, especially microphone. Some apps might work through ALSA and might "sidestep" pulseaudio - these need a ~/.asoundrc file with the following content:
About clients:
As a rule, it is best to have the same clients on both end or compatible ones (such as Android Conversations+Desktop Gajim, Desktop Jitsi-Meet+Jitsi-Meet Android client).
Empathy is in a permanent broken/beta state since forever, using all kinds of frameworks for different protocols never worked out in practice. Gajim is ok for text chat (it uses the newer technologies for encryption and file transfer) but the audio/video uses some external components that are missing on newer Linux versions (at least in Debian).

As for jitsi, that one is very good, i used it with google accounts (until they stopped supporting XMPP) and with my own Jabber server, works fine, it even has end-to-end audio/video encryption. It does not have Android client BTW.

One true cross platform audio/video client is in fact Google's own browser-based Hangouts that comes with the free Gmail accounts - it works very well on Linux and the Android client is well optimized even for low bandwidth.

OSS alternative would be Jitsi Meet (this is a Hangout-like browser-based app that also has a basic Android client, made by the same people developed Jitsi). It works in browsers without plugins (Chrome and Firefox) and has an Android app that is under heavy development ATM but works quite well for audio/video.
Jitsi Meet is open source and can be deployed on your own server if you really want/require privacy.

About bandwidth: Skype on desktop does not use more bandwidth than other audio/video applications. And pretty much all modern apps use dynamic video scaling - this however does not include Gajim/Empathy since those rely on simple mechanics without complex run-time bandwidth/latency checks. I think Jitsi is capable of some adjustments.
Generally browser-based audio/video (Facebook/Hangouts/Jitsi Meet/ Web Skype etc) use the browser's already built-in mechanisms for constant checking of bandwidth/latency and do fine-grained adjustments of video if needed (audio is the top priority and since it already uses low bandwidth it is not typically throttled).

Thank you so much for the comprehensive and constructive reply. I will see what i can achieve with your suggestions. Am away at DrupalCon at the moment.
I did manage to get Viber working, but will get back to testing next week
Regards
Francis