Update your /usr/share/file/magic file?
#------------------------------------------------------------------------------
# pdf: file(1) magic for Portable Document Format
#
0 string %PDF- PDF document
>5 byte x \b, version %c
>7 byte x \b.%c
I'd use hexdump to look at the first few bytes of the PDFs that are not identified correctly.
Update.
How you update the magic file depends on your operating system and distribution. Typically you'd use the package manager. For example on RedHat Linux and downstream distributions that follow, you can use yum provides /usr/share/file/magic to find what package contains that file then use sudo yum update <packagename> ...
$ yum provides /usr/share/file/magic
...
file-4.17-15.el5_3.1.x86_64 : A utility for determining file types.
Repo : installed
Matched from:
Other : Provides-match: /usr/share/file/magic
$ sudo yum update file
Loaded plugins: fastestmirror
Loading mirror speeds from cached hostfile
* base: centos.mirroring.pulsant.co.uk
* extras: centos.mirroring.pulsant.co.uk
* rpmforge: nl.mirror.eurid.eu
* updates: centos.mirroring.pulsant.co.uk
Setting up Update Process
Resolving Dependencies
--> Running transaction check
---> Package file.x86_64 0:4.17-21 set to be updated
rpmforge/filelists_db | 5.9 MB 00:08
updates/filelists_db | 1.9 MB 00:03
--> Finished Dependency Resolution
Dependencies Resolved
================================================================================
Package Arch Version Repository Size
================================================================================
Updating:
file x86_64 4.17-21 base 320 k
Transaction Summary
================================================================================
Install 0 Package(s)
Upgrade 1 Package(s)
Total download size: 320 k
Is this ok [y/N]: y
Downloading Packages:
file-4.17-21.x86_64.rpm | 320 kB 00:02
Running rpm_check_debug
Running Transaction Test
Finished Transaction Test
Transaction Test Succeeded
Running Transaction
Updating : file 1/2
Cleanup : file 2/2
Updated:
file.x86_64 0:4.17-21
Complete!
If you are willing, you can instead update the magic file using a text editor after reading man magic and using hexdump _C -n 20 on sample document files to work out signatures for yourself.
if you are going to do this, it might be prudent to create a separate magic file first and use files -m magicfile option to test it.
P.S.
$ file --mime `locate *.pdf`
/usr/share/doc/bind-9.3.6/arm/Bv9ARM.pdf: application/pdf
/usr/share/doc/libtheora-1.0alpha7/Theora_I_spec.pdf: application/pdf
/usr/share/doc/prelink-0.4.0/prelink.pdf: application/pdf
/usr/share/doc/samba-3.0.33/Samba3-ByExample.pdf: application/pdf
/usr/share/doc/samba-3.0.33/Samba3-Developers-Guide.pdf: application/pdf
/usr/share/doc/samba-3.0.33/Samba3-HOWTO.pdf: application/pdf
/usr/share/doc/speex-1.0.5/manual.pdf: application/pdf
/usr/share/ghostscript/8.70/examples/annots.pdf: application/pdf
/usr/share/gimp-print/doc/users-guide.pdf: application/pdf
Maybe you can upload, to a file-sharing website, some files that file fails to identify correctly.