One possible way around this is to change the color palette in Book.xlt.
Book.xlt provides the default styling that all new workbooks will use. So any styling changes made in Book.xlt will automatically be incorporated in every new spreadsheet created.
In the Office XP version of Excel you can find Book.xlt in:
C:\Program Files\Microsoft Office\Office10\XLStart
(If you are on a different version of Office the 10 will be different.)
If there is not a Book.xlt, create a new spreadsheet and save as Book.xlt (use the file type Template (.xlt) in the Save As dialog box).