they have the meid or sim card id wrong.
you can read the sim card to verizon by going to settings , general , about and reading the ICCID
go back to verizon
however there are a few things you try or look out for
1) if you are in a verizon extended network, like for example, Golden state cellular in san andreas, verizon cannot activate your device, because its not there network. if the phone says "verizon" then it should of activated.
2) the only thing you can try is power down the iPhone. remove sim card. wait. maybe even wait 5 minutes. turn iPhone on. wait for the iPhone to boot up fully and to say "no sim", and then insert the sim. this forces the iPhone to update the sim card and now with iOS 8, this will force the iPhone to get the cellular profile.. maybe this should be attempted while the iPhone has a wifi connection. i think it pulls cell profiles from wifi, like itunes does.
3) EXTREEMLY RARE. if meid is good. sim card is good. iPhone is good. and it still won't activate it is because your billing address does not belong in their territory. this actually happened to me trying to activate the free t-mobile iPad plan!!!!!
back up and sync iPhone before going to Verizon