Are you creating that toolbar manually (via tools|customize)?
If yes, then there could be at least a couple of problems. Excel stores these
customized toolbars in a file with an extension of *.xlb.
#1. You don't have the correct permissions to save that file.
Talk to your Admin to find out why (but I bet this isn't the case).
#2. You have multiple copies of that *.xlb file and the version you're saving
isn't the one that's being opened last. Your version opens and is quickly
superseded by the other version (you may see the changes in you're quick!).
Close excel
windows start button|search
look for *.xlb
in hidden folders and for hidden files.
I'd rename them all to *.xlbold.
Then restart excel and recustomize your toolbar--just a few things for testing.
Then close excel and reopen to see if it worked.
If it did work, then delete the *.xlbold files.
=====
I had a similar problem when I was screwing around.
I use xl2003 under winxp and my *.xlb file should only be in:
C:\Documents and Settings\(username)\Application Data\Microsoft\Excel
(I did have a copy here)
But I also had a copy in my XLStart folder:
C:\Documents and Settings\(username)\Application Data\Microsoft\Excel\XLSTART
Each time I'd open excel, my "real" version would open and then be replaced with
the version in the XLStart folder. I'd modify the toolbar and the changes were
saved into the correct location.
But the next time I opened excel, the XLStart folder version (unmodified!) would
supersede that "real" version.
Depending on your upgrade path, you may have several XLStart folders. That's
why using windows start button|search is useful.
Good luck.