I’ve written a plugin, Next Page, to solve the problem. You’ll get an options screen allowing you to specify the language of your links.
If you’d rather not deal with a plugin, here’s the code you need to add to your page template. I’ve left in a few lines to help with debugging. If your links don’t lead to the pages you expect, you can uncomment those lines to see what’s going on.
$current = array_search($post->ID, $thepages);
$prevID = $thepages[$current-1];
$nextID = $thepages[$current+1];
echo “Current page ID’s array key: $current”;
echo “Previous page ID: $prevID”;
echo “Next page ID: $nextID”;