Basically, wp_page_menu doesn't allow you to replace the container. God knows why, but it doesn't. I'm terrible at PHP, but I've managed to do so with a very basic function:

Code:
function replace_menu_div( $newel ) {
	$html4nav = array();
	$html4nav[0] = '/<div class="menu">/';
	$html4nav[1] = '/<\/div>/';
	$html5nav = array();
	$html5nav[0] = '<nav class="menu">';
	$html5nav[1] = '</nav>';
	ksort($html4nav);
	ksort($html5nav);
	return preg_replace($html4nav, $html5nav, $newel, 1);
	}
add_filter('wp_page_menu','replace_menu_div');
However, as you can see, this little function won't take in new classes. It simply replaces the default div with a "menu" class with a nav and a "menu" class as well.

Help? Suggestions?