Are you sure you're still within an area on the coverage map?
https://publicmobile.ca/en/on/coverage
Removing the SIM isn't exactly necessary, but when I worked for wireless support in a call centre (US carrier) we would get people to do it because it was below the battery and it usually took about 60s, the amount of time that's ideal for a full recycle.
Try that, turn the device off, remove the SIM, wait 60s, put it back together and try again.
Another thing you can try doing is forcing your device to use 3G instead of LTE. I had an issue once where I couldn't get the device to connect to LTE for the life of me, but as soon as I turned LTE off and onto 3G, everything started working.
What type of phone are you using?
