I've heard about that "true" and "false" unlock, but don't know what it means or how to do it. If I bought the phone off contract, shouldn't it be unlocked by default?
It's not a bad iPhone per say, from what I've read about your situation, it sounds like the activation policy is the issue.
Now as to activation policy, without going into too much detail, it's basically a policy that is assigned to each phone when they are purchased. Whether from Apple or a third party.
There is a lot more policies than just unlock or not.
For new phones that have never been used, whether retail new or replacement phones, they check the activation server for what policy they will be assigned. (All iPhones already have an assigned policy but check to see if it has been changed)
Whenever a phone is restored to factory state via downloading the software, it will check Apples server twice. Once to verify if that version software is allowed still and the second time when the phone is being activated to determine what the activation policy is for that phone. If you just erase all contents and settings, it already has the activation policy and will not check the server. (This is why you see when a previously locked iPhone is unlocked, they request you connect to iTunes and restore it)
I'd recommend inquiring about it but do not be surprised if a lot of employees are not very knowledgable about this.