George,
I think I figured out the problem. Our imagery was delivered in .jp2 format (Jpeg2000). These apparently have built in pyramids which seem to cause problems. In order to resolve the issue, I had to do two things:
1. Define Overviews - Outside of the default options, I set the "Number of Levels" parameter to -1 so that it would determine the optimal value for me. Under the Overview Tile Parameters category, I checked the box to "Force Overview Tiles." I think that setting must have convinced it to ignore the internal pyramids and build the overviews properly because when I ran with those settings, it took about 30 seconds longer, and the log was populated with a lot more info. The mosaic layer in the map then updated with new footprints showing the expanded footprint for the new overviews and the imagery was replaced by the black and white checkerboard when zoomed out since the overviews hadn't been built yet.
2. I then ran the Build Overviews tool with the same parameters as before. It took about 35 minutes for ~900 imagery tiles (1527 overviews built) and when it finished the imagery finally popped up. I ran this on my local hard drive so I'm just going to copy the layer to my eGDB now. Thanks for your help!