In order to rearrange the index, SQL Server must put locks on that index. While locked, other users can't get access to it. The way around this is, if you're on Enterprise, to use ONLINE. That uses some of tempdb to store data in order to allow for access to the index while it is rebuilt. Other than that, only rebuild indexes during low load times as was already suggested.

The trick is to understand why everything is locked during the forty minutes it takes to run. It should only be locking on any one index for a short period of time. It shouldn't just lock out a user. You should use sys.dm_exec_requests to understand why that user is blocked and what exactly they are waiting for.