When you look in WordPress source code, you will find reason for that. On line 538 of nav-menu.php you’ll find:
if ( ARRAY_A == $args['output'] ) {
$GLOBALS['_menu_item_sort_prop'] = $args['output_key'];
usort($items, '_sort_nav_menu_items');
$i = 1;
foreach( $items as $k => $item ) {
$items[$k]->$args['output_key'] = $i++;
}
}
I didn’t check why, but it looks like this sorting doesn’t work right. The easiest thing you can do to fixthis is to change output type to disable this sorting.
So when you add 'output'=>OBJECT
or 'output'=>ARRAY_N
to your args it should work just fine.
PS. It’s even known bug: http://core.trac.wordpress.org/ticket/15533