How big are the tables in question? How many pages do the indexes take up (visible in sys.dm_db_index_physical_stats)

Edit: btw, a separate update statistics is not necessary (and may even be counter productive) if you're doing an index rebuild. When the index gets rebuilt, the stats get updated as if an update stats with full scan was run.