Got the plugin to work. Since the new site had a menu of "home" and "Sample Page" I thought there was one created already. When I logged in to the multisite there were no menus setup. So, setup a menu called Placeholder like you suggested and selected that menu and click add. The admin menu now shows on all multisite.
So, this is great, but it requires our users to go in and create a menu on their site. Is there a way to have this automatic. I know in WordPress 2.8 MU, I was able to use code in the template and display one menu across all multisites. Also, I was able to remove the home button on the Admin blog and include it on all multisite pages.
Is there no way to do this in WordPress 3.0 +? Sorry if this makes no sense.
The main reason we don't want each user setting up a "dummy" menu is all the questions on how do I do this. Also, we are going to have 100's of mutlisites using the same Admin menu.