Oh, yes, the generic "nothing found" is the same as 404 message only nicer because it's not so technical and cold.
Something is not right, obviously. My "stab in the dark" was that the old page and the new page had the same name, but that is not so.
Can you try making a custom menu which includes all the pages you want to appear, including the new page. ( http://twogetmarried.wordpress.com/you-need-to-bring-things/ )?
As a volunteer I can't see what's wrong, but if a custom menu makes the new page visible in your menu, then that's all for the good.
and other info you might want to check out about custom menus:
I'll put a modlook tag on this thread as well (so staff will help you), just in case the custom menu doesn't work…