The key to this is issue is removing the battery. When you remove the battery from an iPhone and then replace it. In most cases the phone thinks the date is 1970 Jan 1st. AT this point you will not receive a signal.
The first thing to do is either manually set the date or to connect to wifi and let it set automatically. Then restart the phone with the sim card in and Hey Presto! You will get the signal back.