You don't want to click "change style only", you should click "save" button at the bottom of the options. Basically, the "change style only" says change only the colors, do not change the layout (to over simplify). And incidentally, I'm fairly sure that's a 1.9.11 option, you should probably upgrade to version 2.0.
If you were working on users you may have inadvertently taken away privileges needed to view the menu items. You said that the admin menu has less options than before which could indicate that you've somehow manage to take some privileges away from the admin user (and possibly other users too).
Did you try to re-assign the menu module as I originally suggested?