You can't edit a PDF you didn't create, and the only viable solution to editing at all is to recreate the PDF with the new links replacing the old. If you don't possess the original document you're going to run into formatting problems, font problems, and image problems.
I am browsing through the Adobe Acrobat 9 Pro. It gives me the impression that Adobe Acrobat 9 Pro can open and edit the pdf file,it says "Create and reliably share PDF documents |Easily convert any document that prints to PDF to preserve formatting and ensure document integrity." isn't it so?