"take long" is quite relative. In the enviroment I know we lose data if a table is locked for more than 30 seconds. As far as I have seen the UPDATE-USAGE-command places a lot of locks and on tables with some million records the command runs much longer than 30 seconds.

Maybe - and I really mean MAYBE - you can solve the problem by rebuilding the indexe mentioned in the error message. Depending on the SQLServer-version you use you can do an online rebuild which should hold only minimal locks. I don't believe an index reorg will work but it would be another try.