I am running Exchange Server 2003 SP1. I can download a new address book
just fine but no one else seems to be able. They get no errors but the
changes to the GAL do not show like they do for me.

I am the Exchange Admin but that shouldn't matter should it?