Takes a few hours, although they may tell you 24-48.
Someone here persisted at one point though and managed to force them to unlock his phone within a couple of hours of paying it off.
The problem isn't the actual unlock process - it's getting Sprint to actually submit the unlock request to Apple.