I've seen in my case where an index on one huge table was taking too much time. I did it with SORT_IN_TEMPDB = ON and it completed faster (though still took some time but comparatively). As Nadrek said, you should ensure that tempdb has enough space to perform the index rebuild operation.