I think I found the oddest little workaround for making internal links work for PDF exports.
Export your PDF from an UNSAVED *.md document.
That is to say, once you're happy with your document, create a new document and copy all your content into the new document and do not save it. Just export it to PDF (it'll be saved as "New Document"). Then, change the filename on your exported PDF.
This works for me. I'm pretty stunned as I've been trying to figure this out for hours.
Note: I'm using Markdown Extra with the following reference-style linking syntax as described on Daring Fireball:
# Heading # {#myshinynewlink}
blah blah content
[foo][]
[foo]: #myshinynewlink
The following linking syntax works too:
[foo](#myshinynewlink)
7/25/2016 update: Caveat if you're linking to other media:
Unfortunately, when you do this workaround, AFAIK, local images that you've inserted via relative linking do not get pulled into the PDF. So, if you have images that you're linking to via something like [ImageName](images/image01.png)
, this will cause a new problem for you.
I think you'll be fine if you're OK with uploading your images to a place that's not behind any firewall or security. For example, 
renders correctly when exporting from an unsaved *.md document. But 
does not (of course, it does work on a saved document). Unfortunately, this workaround isn't an option for me because I can't upload my images to a public site (due to confidential/sensitive material).