Call Customer Service and ask for their assistance. The MEID should be both on the phone (often behind the battery) and on the box. Did you compare the two numbers to make sure they match? It is possibly (however, very unlikely) that there was a typo.
You can dial *228 option 1 from the new phone - that will either walk you through activation, or connect you to Customer service if needed.
Is this a phone purchased from Verizon? Off eBay or Craigslist? From a friend? Is it a Verizon branded phone?