If "there's a problem with the MEID", it usually means that the phone's been reported stolen. If it's new, return it to where you bought it (with the receipt) and ask for a new phone.
If you bought it used, you should have been in the carrier's store buying it (you pay the carrier, the old owner gives the carrier the phone, the carrier switches the listed owner to you, gives the old owner the money and gives you the phone - then only you can report it stolen). If you didn't, you have a case of "he sold me a stolen phone". You can go to the police or hire an attorney, depending on which works best where you are.