404 Error lists all pages

Having a strange problem whenever I reach a 404 page or search for a term that isn’t found, my navigation menu lists all the pages on the site and looks screwy. I’ve tried the fix listed here but the same problem continues. Any thoughts on what the problem might be? I am using a conditional submenu to show child pages, so I’m not sure if that might be having an effect.