I have recently purchased (04th June 2013) S4 from a EE shop, 2yrs contract on EE 4G network.
I started having exactly the same problems with the newtwork signal( no signal,not registered on network, no network coverage). The signal is lost intermittently and is erratic.*
I have called the EE technical support and they have asked me to enable data roaming to improve the dignal, but, that didn't help.
It is s breach of the contract, I am planning to return it.