We play multiplayer Stellaris every Friday and currently most weekend days as well. We noticed this in more than 80% of our games, so I wonder if it's something to do with settings as well.
It's extremely rare to see the guaranteed habitable planets now and it's really messing with balance - as it becomes pot luck whether or not people can settle a second or third colony. This needs looking at with extreme urgency as it's a pretty major bug.
For what it's worth, we run mostly default settings. We recently cranked up the AI to Captain for our sessions (even though half the universe is human anyway) and tend to use "Distributed Players" (which btw also doesn't work - we still see players clumped together even when there's plenty of space! This can even happen in smaller sesions with only 3-4 humans, we still end up together - usually one person by himself with plenty of space and 3 others next to each other)
We tend to leave everything else along - though occasionally we may reduce wormholes and/or increase crisis strength. We normally remove advanced AI as we prefer a harder AI over a 'cheating' start. Plus we have some rookie players. Last but not least, we may randomize the number of fallen empires.
Universe is normally standard ecliptical (sp) though recently we also tried ring. We used to only play on arms but this looks quite ugly with the new system.