Initially this plugin didn't work for me either but I worked out why and have been able to fix it. Please bear in mind that if the plugin isn't working for you it is not the fault of the author of the plugin, but the author of the theme that you are using. The theme I was using (Primepress, specifically header.php) implements its own way of getting a list of pages by talking to the database directly rather than going through the correct functions - it bypasses the sorting functions.
I fixed the problem by finding where in the theme (use the theme editor) it makes the database call (probably in the same php file as the data is used) and alter the sql directly from "order by ID" (or by title) to "order by menu_order". For example, header.php in the Primepress theme I changed the following line from:
$these_pages = $wpdb->get_results('select ID, post_title from '. $wpdb->posts .' where post_status = "publish" and post_type = "page" order by ID');
$these_pages = $wpdb->get_results('select ID, post_title from '. $wpdb->posts .' where post_status = "publish" and post_type = "page" order by menu_order');
Also, if you need page ordering in the side bar widget you need edit the widget and set the "sort by" to "page order".
Hope that helps. There are some really shoddy themes out there.
Thanks for the widget!