Per Anthony's post, this is not a document issue and most probably an Adobe issue.  I too noticed this issue after the upgrade from 4.3.2 to 4.3.4 but it was not isolated to the document module.  In fact, it was a Link module and it does not happen every time.  That is, a user could have the "File not found" error occur but then try it again and get the file normally.

Some facts are:

1. sporadic issue with .PDF docs only
2. not isolated to document module
3. spans various versions of acrobat
4. emerged around time 4.3.4 was released
5. reported in non-DNN sites

Personally, I think Windows Update installed an update that interfered with Adobe's Active X control.  Not sure who is at fault (Acrobat or Microsoft) but latest adobe seems to have a fix for it.  The problem is, the latest adobe seems to assert itsef as a PDF suite of applications, not simply a reader.  My users can't download 22 MB to simply view files.  Additionally, the latest adobe installed a mini-Windows Update of its own and keep bugging the user to download an additonal 20 MB of updates every other week.

Workaround:
This worked for my users

1. right-mouse click on download (or title) link
2. select "Save Target as..." and save to hard drive
3. navigate to saved file and open

Also, this issue seems related to the "blank" PDF problem.  That one seems to be dependent on the Adobe version you are running and if the ActiveX control opens in new or exiting window.

There are plenty of PDF creator alternatives (even open source).  Anyone know of good open-source PDF reader alternatives?

IMHO this is an issue with the code for the linkclick.aspx file and associated code behind this as the problem also exist when you have a links module and point to an existing file in the portal.

I have found a temporay work around and it has worked 100% of the time.  Figure out what the full URL is for the document, the put the document in as an external URL.  This appears to bypasse the linkclick.aspx code