Don't know if people have resolved this, but I found that my s6 favours a smidgen of a 4g signal over a strong 3g signal, so by forcing it to just select 3g networks it then worked fine.
If you log on to my vodafone go to sure signal management, then deregister the sure signal. Then you need to re-register it and the phones that can connect to it.
