Sounds as if you have a default color pallet set up in your normal.xls file. Start Excel in safe mode by holding down the Ctrl key when double clicking the icon.
Now, open the spreadsheet and change the colors. Save the spreadsheet. Exit Excel.
Re-open Excel in safe mode without opening anything. Close Excel.
Re-open the file and see whether the colors you want persisted.
If not, repeat opening in safe mode and closing without opening any other file two times before opening the file FROM safe mode, making your changes and saving it.
What did you end up doing four years ago to solve this?