This has the ring of a problem like this: http://blog.teknkl.com/big-brands-bad-code/
But you will have to show me the exact link that generates the 404.
Our backup solution is sending the user to another LP on our domain with a direct link to the PDF file, but we would rather the link be in the email if possible.
Actually, you should be moving away from direct links in email. See the reasons here: http://blog.teknkl.com/stop-using-direct-download-links-unless-you-like-losing-tracking/
Thanks Sanford, and by the way, terrific blog! Bookmarked!