From your post, I've gathered that you're using 2.2.x and you have the Main Menu system block enabled. Your old modules are there, but when you added new modules to your system, they did not show up in the Main Menu block. You also stated that you changed the order # so that they are not zero.
With the system Main Menu block, only modules that the user has permission to view will show up in the block. Verify that users have permission to view the modules, especially Anonymous Users, who typically aren't granted access by default.
If this doesn't help the situation, re-verify that the order # for the modules you are having problems with are not set to zero. It's possible that the values were not submitted to the database.
If neither of these solutions alleviate the problem, feel free to post back.
Well, I hope that helps! Good luck with your site!
"Need coffee, keep away..."