Thanks. Yeah I've tried updating the OS and I've also tried different unofficial ROMs, all with the same result
also, are you sure it's not a hardware issue? if your phone is still under warranty, you might try to return it.
btw this is a known issue for the galaxy s4, just check the length of this thread: http://www.galaxys4forums.net/forum...on/803-samsung-s4-network-signal-problem.html
sometimes software solutions like turning off the 3g/4g and sticking to edge or selecting automatically preferred network provider might help.
Buy on AliExpress.com