Jailbroken iPhone 3GS shows "No Service" after upgrading to iOS 6.1.6
Was the jailbroken phone also unlocked? If so, the phone has probably become locked again, and will only work with a SIM card after it has been unlocked once more.

This is because in some markets, phones are sold locked to a specific carrier, and will only work with a SIM for that carrier. If the phone is unlocked, it can be used with any SIM.

The unlocking process is separate to the jailbreak, and must be done after the phone is jailbroken.