Since you stated that it would degrade gracefully for visitors with Javascript disabled, I can only see two real issues (and one possible issue) that might come up.
Bad For Accessibility
Screen readers and other assistive technologies are often thrown off by dynamic DOM changes. They process & read the page in a linear fashion, and changing the content of the page after it's loaded might not be correctly handled.
There may be techniques to get around this, but I haven't looked into it too thoroughly.
Increased Complexity
Maintaining this kind of site could be tricky. For one example: If you created a new layout and changed the ID of the content area you were replacing with your AJAX links, it could break your navigation scheme in a pretty perplexing way.
This kind of AJAX behavior would also complicate any traffic analysis you may be doing; Google Analytics wouldn't properly register these AJAX loads without a manual call to pageTracker._trackPageview('this_page');.
Adding more complexity to how your page operates also raises the bar for new developers; anyone working on the site would probably have to be made aware of how this behavior affects page loads.
Possible: Slower Page Load on Initial Visit
Depending on how you structure things, this page fetching AJAX code would only be able to kick in after the document was fully loaded. So, only after your visitor downloaded the whole page, and then the Javascript (if it was an external file), and their browser rendered it and fetched the content via AJAX, would they see the page content.
Each subsequent link clicked would be faster, but fetching the first page a user visited would actually take longer than a static version.
The reason I labeled this as a possible issue is that you could always send the first page statically (since you'll have the static version as a fallback already) and then use AJAX for the subsequent links.
For what it's worth, this doesn't sound like a terrible idea to me - especially for bandwidth-sensitive uses like mobile pages. You'd have to carefully weigh the drawbacks to make sure it was worth it in your case, though.