As you can see from Keith's first comment in this discussion:http://www.arcengames.com/forums/index.php/topic,6658.0.html
density of high mark worlds is
difficulty dependent, at least on higher settings. If the density is oddly low no matter how things are set, then that does start to sound like a bug. I haven't noticed a drop in high level planets in my 80 planet game, have you looked to see if this is impacting other planet counts for you or is limited to 120? I'll go spawn a few 120 planet maps and see if the results look odd in my copy.
Edit: Yeah, I can reproduce that, and planet count doesn't matter. The density of III and IV worlds is markedly lower on any size map (tried 80 and 120) than it has been in the past. This must be an issue in a recent update, since my ongoing game (started under and early post-4.0 release) didn't have this problem. That's very strange, and almost certainly a bug. You should list this in the bug tracker.