The first admin of my site has a full Visual Editor with style sheets. I create new users who are admins (their profile page has same settings with original admin) but they cannot set the style of paragrpaphs (no drop-down list with styles). Any ideas? Thanks.
[See the Screen Shot]
You ned to uncheck the box - Visual Editor, the option is located in User's Edit Profile Page.
UPDATE - 1
2 - You might have been disabled the Kitchen Sink, To enable it Click on small button available in visual editor (Right most button) icon or Press - ALT+SHIFT+Z
3 - Or try switching back to default Wordpress theme (TwentyTen or Twenty Eleven) and check if problem persists.