Try re-publishing the page in question, if you haven't already. Maybe make a small change to it (add a character, delete it again) before republishing.
Also, if you've changed permalink type, it can sometimes mess with the links themselves. When you hover your mouse pointer over the shortcut to the page, what appears in the status bar at the bottom of your browser (i.e. where does the browser think it's going to go)? Perhaps the old link is somehow hard-coded into your theme, and by changing the permalink structure you've broken it?