Oh, oh. This is sounding like my order. After 3 go arounds with Verizon (and 2 weeks of time) we could not get them to tell us why the CC for the $35 charge failed. They kept kicking us up to different departments in Verizon and then to our bank, Wells Fargo. Wells Fargo said it looked good. After 2 reorders and the same failure, we finally ended up ordered direct from Apple, per
@StaceyMJ86, where the same CC worked the first time for the entire price of the phone. There is some sort of corner case in Verizon's system that reject perfectly valid CCs.