Give the gift of Drupal. All merchandise is 50% off through 2016.
When the Menu Breadcrumb module is active, block/region assignment via admin/build/block malfunctions and will not display the correct theme when choosing themes from the tabs. Regardless of which theme is chosen, the admin theme is always shown.
Disabling the menu_breadcrumb module fixes the problem.
There is an issue logged against core at http://drupal.org/node/281643 that suggests that this behaviour can be caused when a call to theme() is made from within a module's hook_init(). Glancing quickly at the menu_breadcrumb code there doesn't seem to be anything obvious there, but there may be a theme call within one of the various functions called from menu_breadcrumb_init ?