Asmodean_dk,
The ability to build terraforming improvements has to do with the amount of available land, which every planet has. Sometimes high class planets don't have many tiles to clear because the land isn't there.
How to tell if it has available land?
Simply look at the map, on a normal map the land is obvious (usually a shade of brown/grey/green) where water is usually blue. So if all the land is already covered with tiles none of the lower end terraforming would be available as it needs high land content in order to terraform. The higher end terraforming also still requires some land available to, don't know the math but somewhere around 30-40% for the best terraforming tile.
The last terraforming tile in most races allows any tile to be terraformed (with the exception of the Altarian Tech Tree) therefore 1 tile on the map even if completely in water can be terraformed.
Extreme worlds it's a little more tricky when it comes to seeing available land especially Toxic Worlds as both the land and water appear green but it uses the same formula.
