It could be a couple of things.
If the users don't have write access to the folder that holds that *.xlb file,
then any change won't be saved when excel closes (and saves the changes to the
*.xlb file).
Maybe your IT Staff decided that the users shouldn't have this ability???
Second (and I'd check this first <bg>), I'd look for multiple *.xlb files on
their pcs.
Use Windows Start button|Search to look for *.xlb
Make sure you look for hidden files in hidden folders--else you won't find all
of them!
I'm betting that some of your users have a *.xlb file in their XLStart folder.
So excel opens, loads the real *.xlb file, but then sees this additional *.xlb
in XLStart and loads that, too. It replaces the "real" one.
Then the user customizes the toolbar.
When excel closes, the "real" one--not the one in XLStart gets changed. But the
next time the user opens excel, the same thing happens and the copy in XLStart
supersedes that "real" version--and it looks like no changes are sticking.
======
If worse comes to worse, the user could delete all the *.xlb files found and
create a new one from scratch.
But if they miss finding the one in XLStart, then they'll have the same problem.