Yep, you typically have to backup your iPhone and restore via iTunes to "push" through the unlock on Apple's servers.

That restore process in iTunes is switching the current carrier activation policy to the unlocked activation policy after your IMEI is unlocked.