Get next/previous cousin page

I solved this by getting all pages, assigning them by level, and then getting the next page of the same level. If you also want the previous page then you should probably cache the functionality that groups the pages by level.

function wpse16875_next_page_same_level_link()
{
    $next_page_same_level = wpse16875_next_page_same_level();
    if ( $next_page_same_level ) {
        return '<a href="' . get_permalink( $next_page_same_level ) . '">' . get_the_title( $next_page_same_level ) . '</a>';
    }
    return '';
}

function wpse16875_next_page_same_level()
{
    $current_page = $GLOBALS['post'];
    $current_page_level = null;

    $all_pages = get_pages();
    $pages_by_id = array();
    $page_ids_by_parent_id = array();
    $page_ids_by_level = array();
    foreach ( $all_pages as $page ) {
        $pages_by_id[$page->ID] = $page;
        if ( ! array_key_exists( $page->post_parent, $page_ids_by_parent_id ) ) {
            $page_ids_by_parent_id[$page->post_parent] = array();
        }
        $page_ids_by_parent_id[$page->post_parent][] = $page->ID;
    }
    foreach ( $all_pages as $page ) {
        $ancestor_page_id = $page->post_parent;
        $level = 0;
        while ( 0 != $ancestor_page_id ) {
            $ancestor_page_id = $pages_by_id[$ancestor_page_id]->post_parent;
            $level++;
        }
        if ( $page->ID == $current_page->ID ) {
            $current_page_level = $level;
        }
        if ( ! array_key_exists( $level, $page_ids_by_level ) ) {
            $page_ids_by_level[$level] = array();
        }
        $page_ids_by_level[$level][] = $page->ID;
    }

    $current_level_page_ids = $page_ids_by_level[$current_page_level];

    $current_page_pos_by_level = array_search( $current_page->ID, $current_level_page_ids );
    if ( array_key_exists( $current_page_pos_by_level + 1, $current_level_page_ids ) ) {
        return $pages_by_id[$current_level_page_ids[$current_page_pos_by_level + 1]];
    }
    return null;
}