If your original phone was unlocked, you replacement phone will also be unlocked. There is no need to unlock it again. You can simply activate it with a valid SIM card of your choice.
If your original phone was not unlocked, you should have no issues getting it unlocked with the IMEI you have. The database for unlocking your iPhone is owned by Apple, so if it exists on the their database, you should have no issues.