One of the big downfalls of purchasing an iPhone from a non-official source is a mess like this. Only the carrier that an iPhone is locked to can authorize the phone's official unlocking. Just about every carrier that unlocks iPhones will only do so for users active on their network. Thus, you're gonna have to establish service with the carrier this phone is locked to(after verifying they offer unlocking), then request they unlock your phone.
Unfortunately, it seems you were misled. ONLY the carrier it is locked to can authorize the unlock. Apple Care may be able to tell you what carrier that is. You may just want to consider seeing if you can get your money back if that's possible. If it is locked to AT&T, which many of these seem to be, then you're out of luck. AT&T will not unlock iPhones for any reason.