If you bought it new, as the first user, then the IMEI should not be blacklisted. Blacklisting is normally done to render a stolen phone inoperative (note that "stolen" includes "someone bought the phone at a subsidised price as part of a contract then decided to stop paying the contract payments and sold the phone" - the service provider considers that to be theft, since they broke the contract before paying off the phone, and blacklists the handset).
A much rarer reason is if someone "clones" your IMEI. If two phones with the same IMEI are detected on the network this will be seen as a sign of wrongdoing, and most likely blacklist that IMEI (blocking both phones). This is why you never post your IMEI in public.
Unfortunately if it is blacklisted it can be very hard to do anything about it. Providers are usually unwilling or even unable to remove a blacklisting if the reason is that the phone is listed as stolen (for obvious reasons: there's no disincentive to theft if someone can just call up and get the blacklisting removed). Ironically the main reason for "cloning" (reprogramming the IMEI) is because the original IMEI has been blacklisted - I should add tha the practice is also illegal in many countries, and I do not recommend that as a solution! Hopefully your problem will not be due to blacklisting.
I suggest speaking to your service provider to check whether they have any idea what the problem is. You can also tell them your IMEI and ask them to check it isn't blacklisted.