wp_head() and wp_footer() are absolute requirements for any WordPress theme. Without them, themes, plugins, and WordPress core can’t enqueue scripts and styles that are crucial for the correct functioning of your site. (So if something has to go, it’s the menu plugin and not wp_head()).
Unfortunately, a lot of plugins don’t actually implement their styles and scripts correctly and so can conflict with other correctly implemented plugins.
Looking at that specific plugin, I see the following entry in the changelog for the newest version:
Fixed CSS file loading setting bug
Are you running the most recent version of the plugin? It’s possible you’re seeing that very bug.
As @m0r7if3r says, you should try using Twenty Ten to see if the that resolves the problem (in which case it’s a theme issue). Otherwise, try disabling all the other plugins, reenabling them one by one, and watching to see if another plugin is conflicting with the menu plugin (the problem plugin could be the menu or a second plugin).