you can send me your IMEI and i can check for you if you like to make sure if its locked or unlocked (I provide unlock services to 1000's so on worries about privacy)
As strangely as it sounds, I had a similar issue, where I had a Bell iPhone 5 Unlocked, replaced, used on Telus and Fido for 2 months each. Then when I came to the States, it turned out to be locked to Fido...Apple didn't help me and I ended up paying Fido $50 to have it unlocked because they claimed it was their phone...my situation was probably rare - lets hope yours is resolved sooner and properly.
Do located your previous iPhone 5 IMEI #, have proof of your $75 payment and take it back to Apple otherwise, show them that you paid and it should be unlocked....besides from my one bad experience, all my iPhone replacements have come unlocked as the phones being replaced were Unlocked.