wp_nav_menu() has a filter, wp_nav_menu_args, right after it parses the function arguments. This essentially allows you to change the menu at any time. So, if you want to have a different menu for administrators, editors, authors, contributors, and subscribers, you can easily do this via the wp_nav_menu_args filter hook.
First, you will need to check the theme_location of the menu. If you utilize menu theme locations, as your theme should, then any time the location is empty, it is because of the Custom Menu widget. Personally, I wish WordPress would have placed that in the arguments; however, as it stands now, 3.4.2 and 3.5.0, it is what it is.
Use Justin Tadlock's Members plugin to create new roles and new capabilities to further expand this.