I'm sure part of the issue is understanding color schemes.

This should help you get started with how 2003 handles colors:

http://www.echosvoice.com/colorschemes.htm

http://office.microsoft.com/en-us/powerpoint/HA102464571033.aspx?pid=CH100740871033
may help a bit with 2007.

Basically, though, 2007 has 4 colors dedicated to text and backgrounds --  
two combinations of light/dark. This is so the text doesn't disappear on the
background -- when the background is changed to dark, the text is light, and
vice-versa. Usually PPT 2007 takes the background and text colors from 2003
and duplicates them for 2007. Then it uses the background color and title
text color (or sometimes the Shadows color) for the 2nd combination of
light/dark background/text.

But if you've used a different color from the color scheme in 2003 for the
text or background, then PPT may interpret that incorrectly when it grabs
the color schemes from 2003. Also, if you look on the 2007 design tab in the
Colors dropdown, you'll probably see 10 or 12 extra color schemes. These are
created from all those extraneous color schemes in the 2003 file. If you
delete those from the 2003 file, that may help.

But you're saying you have a 2007 file, and your 2003 clients are having
trouble. I suspect it's still a matter of color schemes and how they're
being applied to the objects. The principle of the color schemes is the same
in the two versions, so reading that stuff about color schemes in 2003 may
at least help you get started with troubleshooting. You may want to consider
creating a 2003 template specifically for 2003 users, though. Going back and
forth is hard.

I will have to write something up about this. Opening a 2003 file in 2007
gives this, in additon to what I said above about Text/Background combos:

2007                2003
Accent 1        =        Fills
Accent 2        =        Accent
Accent 3
Accent 4
Accent 5
Accent 6
Hyperlink         =           Accent and hyperlink
Followed Hyperlink        =        Accent and FH

I don't know how PPT generates Accents 3 through 6.

Opening a 2007 file in 2003 gives this:

2007                2003
Text/Background Dark 1        =        Background
T/B Light 1        =        Text and Lines
T/B Dark 2        =        Shadows
T/B Light 2        =        Title Text
Accent 1        =        Fills
Accent 2        =        Accent
Accent 3        =
Accent 4        =
Accent 5        =
Accent 6        =
Hyperlink       =        Accent and hyperlink
Followed Hyperlink        =        Accent and FH

So part of the issue may be that accents 3 through 6 don't actually show up
in the 2003 color scheme, but the Hyperlink and FH colors do. However, those
aren't available on most color pickers in 2007 -- they only appear in the
edit color schemes dialog. (That's by design.)