In general, the default color palette is hardcoded. The best way in my opinion to workaround this is to integrate a sample slide, where the user can change the colors.
In Powerpoint 2003 you can customize the palette for bar charts
01. go to slide design
02. choose color schemes
03. Than edit color schemes (its small and at the bottom!)
04. CUSTOM TAG > choose a color and CHANGE color.
This will help I hope
APPLY