If you create a page, then add a link to it from one
that didn't
previously have one, does it still show up red (i.e. action=edit)? For
that matter, if you edit one of the pages that has these broken links
on (not necessarily touching the links themselves, just making a dummy
change somewhere) do they then render correctly?
They seem to render correctly in both cases you describe.