From IIS go to _layouts/images/(img name) and check
the enable anonymous access.

Just curious... Why do I need to allow anonymous access. The default
sitelogo.gif has windows authentication enabled and not anonymous
access.

How did you access this folder   /_layouts/images?
I need to go to the IIS manager and drill down to the default  website to finde the _layouts web etc.
Could it be that you are actually putting the image file  in a _layouts/images folder under your local Inetpub/wwwroot ?
Maybe that is why it can find the image to load on the page when you try it and not when others are trying it.

The way I accomplished the task is as under:

Copied the .gif file  to the location  /_layouts/images in which I found the sitelogo.gif file (SharePoint's default logo  file)
Went into IIS Manager, selected Web Sites, CompanySite (I did not use the default  web site, but I guess that does not matter) -> _layouts -> images and I found the gif file that I had inserted

Is this the correct approach, can you add a gif file directly in IIS Manager in the _layouts/images folder  ???

The only file  that physically exist in webroot is web.config. Rest are the
pointers to other resources.

/_layout is actually mapped to C:\Program Files\Common Files\Microsoft
Shared\Web Server Extensions\60\template\

In tha mapped directory you will find the images directory you will find the
images directory as well. That's where you should put  the image files.

I am not sure what you mean by directly inserting a file in IIS. You can
directly update/replace a file using FP2003 which actually updates/replace
the file in C:\Program Files\Common Files\Microsoft Shared\Web Server
Extensions\60\template\images.

I had this problem  also, but figured the solution. I am not sure
why, but when I put  the new logo  file in the same folder, I
neglected to check the NTFS permissions, and I had not altered one
of the original pictures (therefore it did not have the same
permissions).

Needless to say, I got the exact same problem. If you compare the
permissions on your new file  with others, I believe you will find
they do not match. If you change  the permissions to match, it should
work fine.

I did not enable anonymous, though it seems that might work. My
customer is pretty picky about security.