I am having this problem, I have been with Fido for 14-15 years, but their service never gave me that much trouble, running a small buisness for Drivers Training, and 99 % students use text, this Lazzy and lathargic approch by Fido to fix my phone is un-acceptable.
**Edited to add label
Samsung Galaxy S4
got from Fido, currently no Antivirus installed, I even factory reset my phone twice, plus bought a new sim card as advised by Fido tech on phone.
very very late but lathargic technical support.
@shakman959 try disabling LTE set the phone network on GSM only or any other setting without LTE and see if it will work.
EDIT:Also try clearing the cache partition on the phone and clearing the cache for the messaging app. To clear the cache for the messaging app go to settings then apps and look for the messaging app tap on it then go to storage and clear the cache in there, restart the phone and try sending a text.