Ok mortili is right it has to do with the amount of landmass, the game seems to generate a randomization of the ultimate quality of the tiles on a planet but the basic landmass is determined by the DDS file for that planet. It is possible to terraform every last tile on a planet but the generation system for planets seems to adhere to a lower limit of tile quality it will handle.
The issue you are seeing with terraforming is that each type of terraforming contains <LandPercentageMin>0.35</LandPercentageMin> this one is for the first terraforming tech.
Meanwhile this <LandPercentageMin>0</LandPercentageMin> is for the biosphere manipulator which is the penultimate terraforming tech and will essentially terraform any tile on any planet.
If you really really want a fully terraformed homeworld at game start just add this trigger to your AbilityDefs.xml
<Triggers>
<OnEvent>OnStartTurn</OnEvent>
<CriteriaTurnNum>1</CriteriaTurnNum>
<PerformAction>
<Action>TerraformTilesOnPlayerPlanets</Action>
<ValueParam>50</ValueParam>
<ValueParam>60</ValueParam>
<ValueParam>0</ValueParam>
</PerformAction>
</Triggers>
Select the ability you added it to, and your homeworld will start out with every tile terraformed at game start. Without actually needing to monkey with PlanetDefs.xml