It very much depends on the type of your application the operation it is doing. Ideally user should always be in control, but there are situations when you will want to keep control when you are making critical changes.
Firstly, you must inform user that a following operation might take X amount of time and that she may not be able to use the system.
When you tell such a thing, this puts a certain amount of stress on the user. You should try your best to alleviate that stress. Best way is to show the time left, and what exactly is the action you are performing. While doing so, your messages should avoid jargon and meet the target audience's vocabulary.
A windows update may not be an precise example for this situation but it does tell you how Microsoft handled it in Windows 7.
Although here Windows can not estimate the time required, it tries to break up the operation in steps so that user has some tangible progress to hold on to. This is very essential for many reasons. I have seen vague progress bars which just run to oblivion without offering any solace to users. You must avoid that.
Considering your use case, after user feedback, you might want to push the message of delay when the operation does not complete in threshold time. I agree that users would already have started the process, but if most of the times the operation is going to take few seconds, there is no reason to always show a message that they can't use the system. After a few seconds you can pop up and mention this seems to be taking longer than usual. You might need a users opinion on this.