What plan are you currently on? Try restoring iOS via iTunes to make sure you have a clean state again. Afterwards, try putting in the Fido SIM and let it activate. Then. try seeing if you can text someone. By the way, Is this iPhone 4S a locked FIdo one or unlocked one?
If the above doesn't work, try calling in to FIdo customer support.