The first test to see why it's happening is to see if the IMEI is blacklisted for being lost/stolen, or nonpayment. You can do this here. If it's blacklisted on one carrier, it's useless for all of them now. If you find the IMEI is bad, the best thing you can do is find the owner, or take it to the police and have them hold it for the required time before it legally becomes yours. Do not sell it or change the IMEI.
Changing the board is also a major risk. It could be blacklisted, damaged or good. You may not know until you find out it is still attached to an account, or blacklisted until you know you got screwed. Your safest option is to call the carrier and ask them to try and allow it, but this will almost certainly not work. They only help the original person who signed the contract.
What you can try to do is restore the phone in Recovery Mode, to see if it's bad software or carrier files and it needs new files from Apple's carrier activation server.
To do this, you need to press and hold the power button and home button until the phone resets, and then when it gets to the Apple logo, let go of the power button. The phone should enter recovery mode. This won't fix every case, but it's worth a try.
If that doesn't help, it's a baseband issue. This means you need a new motherboard, since the baseband chip is married to the board it's installed on. You really can't swap this easily. It's best to consider a baseband failure phone junk. The baseband chip that failed is on the board. Changing the antenna does nothing.