By default, on 404 Not Found pages:
- The "Main menu" block, the "Secondary menu" block, and any other menu-based blocks are turned off. This is because, by default, the site_404 variable is blank, so there's no active menu item and, thus, menu_get_item() returns FALSE and menu_tree_page_data() will return no data. And since menu_tree() relies on menu_tree_page_data(), there's no menu trees.
- The Primary links and Secondary links of your theme are turned off. Again, menu_primary_links() relies on menu_tree_page_data().
So, basically on any 404 error page, all of your navigational menus are turned off. Considering that allowing a visitor to navigate away from a 404 error page is essential, this seems like a pretty big usability fail.