pulls in data regarding the layout of the database table and the block structure underneath.

This information tells the optimizer whether or not it's worth it to use an index or just to hit the entire table to find a row (or a set of rows).

Example: if you have a table with 4 rows in it (believe it or not, we do) (ahem, provided that they are small rows) it's probably not worth the extra expense of going through the index. Just grab the entire database and look for the row that meets the criteria.

However, tables change over time (well, some do) getting more data....losing data, etc. If your table started off with 4 rows and has since had 100,000 rows added, it may approach the data wrong. Before, it was worthwhile to pull the whole table (table scan) and now it'll be an expensive (time-wise) operation. Gathering statistics tells the database to go update itself.

I would've thought Oracle had evolved to the point where gather statistics was a background process now.

I'm surprised they had you run gather statistics against an empty partition. If something in the statistics database was corrupted, this would have the possible effect of resetting it back to 0. But I would've thought they'd have you run gather statistics again against the real data.