I have a web app with the main navigation in the left rail. One suggestion that has floated up is to give users the ability to rearrange the navigation. This would serve the purpose of putting nav items that they use more frequently higher in the nav (sometimes it can grow quite tall due to user generated content). This seems a little awkward to me. Would giving users the ability to have a list of 'favorite' links be a better idea? That way the main navigation structure would be the same for all users, but each user could have a 'quick list' of pages from which to choose.
Navigation can be handled very differently, and you seem to be stuck inside with a very common problem: How much control do I give to the user? At first we all say the more power users got - the better. And this can be true in some cases but not all. You have an extra element in the form of many links, which would need some information architecture to be done. Organize content in related groups and try to avoid too many links, since it may confuse users. Of course you'll get a more deep navigation, but that isn't always bad. It's much better letting the user click seven times always knowing where she is at all times, instead of three confusing click.
In your case I'm all in favor of not letting the user control navigation. However, using favorite linking is another story, and something you can constrain to a maximum of 10 favorite links. Favorite also make sense in the mental model users have. At least if they use windows from time to time where favorites have been possible since Windows Vista:
I would have to say giving the users the ability to change/rearrange the main nav would be a little iffy. This falls into the battle of user centric vs. User driven design almost. I am a strong believer that the user does not always know what they want, and rather it is our job as designers, to know what is best for them after we collect feedback in what they want.
Allowing them to create their own heirachy may lead them to disengage in other functionality behind other items. This will disrupt the main success flows that your app should suggest.