What account did you use to add  the pdf16.gif file and modify the
docicon.xml file? Sounds like a NTFS permissions issue.

We used an account setup specifically for SharePoint that has Domain
Admin privileges.

After reviewing some of our support tickets it looks as if the
Windows login  prompt is inconsistent. The support tickets state
that there are instances where users are prompted  for their Windows
login and instances where they are not. I was able to replicate
the issue yesterday by navigating to any site  that displays a pdf,
however today I can navigate  to any site that contains a pdf
document and not encounter the Windows Login.

Additional Info:
We have a medium server farm. 2 Front-ends, 1 Index, and a SQL Svr

I've encountered this before. You likely copied and pasted PDF16.gif
from one location into the images folder. When you pasted it, it
maintained the original security permissions.

What you need to do is set the security properties of the image so that
it inherits from the parent folder.

This should resolve your problem.

Under the properties of the PDF16.gif, Security tab > Advanced, the
Inherited From column had "not inherited" in place of
the "c:\Program Files\..."

Great tip! Looks like that was what was causing the issue. I will be
monitoring it over the next few days.