Would jQuery .parent() be an option for you?
jQuery('.current_page_item').parent().addClass("classname");
If not you could write your own iteration code for the nav menus and check the various conditions as you assemble the list, but I’m guessing this would be a lot easier.