I can't find a way to allow registered users to add pages to the main navigation.  When I try this I get an error after I add the page that says: 

 "An error occurred while adding a page:   You do not have permissions to add or move pages to that location. You can only add or move pages as children of pages you can edit."

Since the main navigation is not a child of anything I can't figure out where to change the permissions to fix this.  Any help wouldbe appreciated.

One possible trick around this is to create a new page which sits above the main navigation (though probably a good idea to take the admin menu out) and give the page editors group page edit rights to this page. This makes all the pages below it child pages and allows the users to add edit the pages underneath.
You will have to make some changes to the menu display in the skin to stop the new page from appearing or disrupting the menu structure. This should be easier though than creating a new module.
HTH
Antony