Default [Q] Help With SIM and ROM

Hi,
I recently rooted my Samsung GS4-i337m variant.
I had a SIM that worked pretty well. It used to go out a bit, but a reboot would work fine to get it working again every few days.
After everything was fine, and working stable, I decided to install a ROM.
I installed PA, and verified that it was the correct ROM, for my model.
It worked quite well for a few days. The SIM had the same problem as before, but a reboot would work fine, like before.
Today, I had time to get my SIM changed, and after doing so, after rebooting the phone, it immediately refused to use the SIM card. It did not give a warning, but simply said "No Service." After trying to go through multiple settings to no avail, I decided to restore to an older backup, from my stock ROM.
I tried this, got an error, and had to stay with Paranoid.

I still have the same problem.
So, are there any solutions to this?
Any app or setting to fix this?
The phone is not unlocked.

tl;dr:
Phone used to work fine on PA, and after changing SIM, it rejected the SIM. Help.