The only guess I can make, apart from a possible bug, is
that IDS:
locks table and indexes in exclusive mode
for every row
1) moves the row in the new dbspace
2) for every index
  a) looks for the corresponding row
  b) updates reference to point to new location
unlocks table and indexes

In fact, a table can be partitioned on multiple dbspaces
and the index itself may be partitioned too, so I think
that each index pointer must be updated to new location.

The expensive operation is 2a. In fact, indexes may be
non-unique too, so IDS must look for the rowid to
achieve maximum generality, and this is a sort of
"inverse-lookup" operation, maybe slightly optimized
using a "first isolate matching keys, then look for
the one with the right rowid" approach.

This is just an hypothesis, but it may explain the
behaviour.

Possible tests to confirm that:
1) retry fragment rebuild with just a couple of indexes
  (is time proportional? if yes, the hypothesis may be correct)
2) retry fragment rebuild with a later release,
  migrate and attempt fragment rebuild again
  (is time regular now? if yes, a bug may be involved)

BTW, another idea, have you tried disabling indexes
before reorganization and enabling them thereafter?

SET CONSTRAINTS, INDEXES, TRIGGERS
FOR table
DISABLED ;

ALTER FRAGMENT ON TABLE table INIT IN dbspace;

SET CONSTRAINTS, INDEXES, TRIGGERS
FOR table
ENABLED ;

That's another possible approach,
  less efficient than index drop&rebuild,
  does not reorganize index storage too,
but
  does not require SQL creation statements
  can be made automatic via scripts more easily

Another interesting test to see it that makes a difference.

The bottom line is that it's better to follow the approach:
- drop constraints/indexes
- reorganize tables
- rebuild indexes/tables
to the maximum possible extent, expecially if tables are big.

Hoping that helps and waiting for feedback if you succeed
in finding the chance for further testing... ;-)

Umberto Quaia
(umberto.quaia@tin.it)