If you are using a System theme (created by the built-in Theme Designer), the reason for this is that the Theme Designer doesn't "know" about any new Menu or Ad Regions that you might have created, so it hasn't yet generate any CSS code for them in your existing theme yet. This will cause your new Menu or Ad Regions to not function or format properly. For example, the width and height of your Ad Regions and Menu Regions will not be set yet so the default size may not fit your page correctly.
So, each time you create a Menu Region or Ad Region, you need to 'refresh' your theme by:
1) Navigate to any Page that displays the new Ad or Menu Region.
2) Click on "Preview Themes" buttom and then the "Edit" button next to it to launch the Theme Designer
3) Find the "fold" in the Theme Designer's sidebar that matches the name of your new Menu Region or Ad Region, adjust the properties as desired and click 'Update Preview Pane' until it looks right.
4) "Save" your theme to generate the code for the new Menu or Ad Region. (You can also "Save a New Copy" in case you don't want to save over your original Theme for any reason).
(Be sure to refresh your browser cache to see the changes take affect).