I really don't think we are going to get a specific answer to this one.
But, think of it this way. Almost every single website out there is designed using a certain percentage of replication across pages. I agree with tedster that the search engines can easily detect what is navigation and what is content. It's the content portion that we should be discussing, not what appears on each page naturally as part of the design.