Long story short, a French iPhone 4 with an Orange.fr SIM that was apparently locked did not work after an update from Jailbroken 4.1 to Apple iOS 7.0.4.
To fix it I installed a Rogers SIM that wasnt active, then iTunes would activate the iPhone again so it could be used as an iPod Touch.
I cut the Rogers SIM down to be a micro SIM using a template found on the Internet.
The Orange SIM could be put back in the iPhone after that point. It wasn’t providing service in Canada before or after anyway.
The Evasi0n jailbreak worked when tried three days before writing this.