buckworks - 12:42 pm on Jul 4, 2010 (gmt 0)
Yes, the menu DID rearrange the structural order of my content.
I suspect that detail is significant.
How many navigation links does a spider now have to wade through before it would reach the unique core content of the page? How does that compare with the previous version?
Something has clearly changed the SEO balance here and if the menu is large, and coming earlier in the source code than it used to, it would be my prime suspect.
Some tweaks to your CSS positioning might be worth testing here, to keep the same visual appearance for users but present the menu later in the source code.