I have checked two colonies which refuse to add inhabitants. If ever, one of them gains 10 pop and the other one actually loses population.

There are no crops or house shortages.

Only thing is it seems there is a Labor shortage.

What is going on?

If you have a labor shortage you probably need more housing as that is exactly what that means, especially if you have reached your colonies max population while having that labor shortage. Not sure that the AI can sabotage an enemies population with spy missions.