Menu doesnt appear on custom 'not found' page
Drupal doesn't render the region of your theme that your primary menu is in; there's a module to change this behavior:


  On 404 Not Found error pages, Drupal will skip rendering of several
  pieces of your website for performance reasons. Some of these include:
  
  
  The "Left" and "Right" regions of your theme.  
  The "Primary links" block and any other menu links block.*  
  The Primary links and Secondary links of your theme.*
  
  
  *Unless you have configured a "Default 404 (not found) page" on
  admin/settings/error-reporting.


From 404 Blocks module description.