In the recent release of wordpress 3.2.4 and the 3.2.3 security release, a change was introduced that caused custom navigation menus to default to the standard page list menu of EVERYTHING!

Not ideal, and as most people found out, the fix for this was to add 'fallback_cb' => false to the wp_nav_menu() calls in their theme, however for me, and some other people, this didn't fix the problem alone.

In fact as well of this, for some people, including myself, it seems that the wordpress upgrade ALSO removed the association between menu locations and the custom menus themselves from the database (i.e. The values set in the "Theme Locations" section of the menu editor were lost.

So, if you're still having issues with custom menus in wordpress, and your code for creating them and including them in your theme appears correct, check the menu editor and see if you need to re-associate your menus to your theme locations!