Toolbar and menu customozations are saved in a file named Excelxx.XLB  where xx
is your version of Excel.

Usually will be located at......................

C:\Documents and Settings\username\Application Data\Microsoft\Excel

Maybe you don't have permission to save to that folder or the folder in which is
may be stored if not that one.

Have a look for *.xlb file using Windows file search.

See where it is and note the size and date.

Make some changes in Excel to a Toolbar, close Excel and see what happens to
your *.xlb file.

Gord Dibben  MS Excel MVP