A Google Webmaster Help thread has Googler JohnMu sharing a tidbit on how not to have your navigation menu structured.
The thread has a webmaster complaining his site dropped in ranking. It appears the reason the site dropped was because Google felt the site was keyword stuffing and spamming. Why? Well, he had most, if not all, of his site's structure in the footer navigation menu. John explained this often might be confused with keyword stuffing and result in a penalty of some sorts.
In general, having a full "sitemap" in the footer rarely helps, and might be mistaken for an attempt at keyword stuffing. Using a normal HTML-sitemap page is probably a better idea -- or just linking normally between the pages in a way that gives context to each page as you're doing now. So given that change, I'd let it settle down a bit now, and just generally continue working on your site.
Now I should add there are many sites out there, including this one, that puts a tremendous amount of the site's structure in the menu and navigation. I don't put it in the footer but I do put a nice portion of it in the top menu bar. Not all of it, because that just isn't useful.
I do not know exactly how much of the site's structure he had in his footer menu bar, but it does seem like he put it all there.
So just be careful how you handle your menu and navigation structure. Make it useful for the user and you should be fine.
Forum discussion at Google Webmaster Help.