Is the virtual directory for the image gallery thumbnails properly set up in IIS?

Yes, and I have checked the filepermissions aswell.

Are you using EPiServer supplied templates or created your own? Maybe you need to set access permissions for images explicitly? See CommunitySecurityModule from Relate Sample Site source code.

ImageGalleryHandler.Instance.ImageAdded += new EPiServerCommonEventHandler(ImageGalleryHandler_ImageAdded);

And then:

void ImageGalleryHandler_ImageAdded(string sender, EPiServerCommonEventArgs e)
{
    SetAccessRightsForEntity((Image)e.Object, ((Image)e.Object).ImageGallery);
}

Which actually turns into:

if (user != null)
    EntitySecurityHandler.Instance.SetAccessRights(entity, user, accessRights);
else
    EntitySecurityHandler.Instance.SetAccessRights(entity, group, accessRights);