Here's a screenshot of my current TA galaxy:
http://i3.photobucket.com/albums/y64/dustbuster87/GC2TA_TerranAlliance_1210012764.jpg
Settings: Immense, abundant stars, common/occasional planets, very slow tech.
9 Major civs, 8 Minor civs, Painful difficulty, AI using max CPU.
The problems are the Yor and Drengin (on the left and right sides of the map, respectively). Neither of them have colonized any planets beyond their home system, and they've done very little research, if any. They've built a couple of mining starbases, but they each have at least half a dozen colony ships in orbit around their home worlds.
It's possible they've just been extremely unlucky and haven't come across habitable planets yet, though, and it's not actually bugged. Does the AI not scout for planets with its colony ships?