Check to make sure you didn't damage/disconnect the cellular antenna when removing or inserting the battery. It's cable runs along the spear assembly parallel to the bottom of the battery. This link shows you where it is and how to replace it. iFixit_Iphone_4s_Cellular_Antenna_Replac... If you need the part: iPhone-4S-Cellular-Antenna
You may also have a damaged cable. If you put stress on the cable the ends, where the plugs meet the cable, start to wear and bend. when this happens the wires inside your cable may break or short out. Try using a cable that works on another device, if that works replacing your cable is the solution.