The first test to see why it's happening is to see if the IMEI is blacklisted for being lost or stolen, or for nonpayment. You can do this here. If it's blacklisted on one carrier, it's useless for all of them now. If you find that the IMEI is bad, the best thing you can do is to 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 that it's 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. This will allow you to see if the problem is caused by bad software or carrier files and if the phone needs new files from Apple's carrier activation server.
To do this, 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 to replace the logic board, 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.