My phone was replaced and it was instant. Looks like someone forgot to add the new phone to your applecare when they were deleting the old one. Definitely contact Apple.
It can take a while, when I did an exchange, it took a while for the apple care plus to go in effect. But I have my receipt to prove that I have applecare+ on it.