I’m having the same problem. No matter what I do, the pages on the menu don’t show up in the same order as in the admin interface.
I’m running WP 2.8.3.
I’ve downloaded the page menu editor plugin, and it does a good job of rearranging the pages order in the Pages display in the admin interface, but it has absolutely no effect on the page order on the sidebar menu that the user sees. I’ve tried several different templates with the same result.
I’ve tried changing the page title, the page numerical order, burning incense and beating a tambourine, to no effect.
I tried finding the sort_order line in practically every php file both in the theme and in the WP core and couldn’t find it. I don’t really feel comfortable messing with the PHP code anyway and I don’t feel I should have to do that in order to get the page menu tuned. I’ve even gone into the MySQL db and changed the ID number of the latest revision of this story, but that didn’t work either.
Frankly I’m about to bail for Drupal, where you can do this kind of menu tuning out of the box.