Creating

If you are unable to find a colour scheme which you like you can create your own.
It is possible to change any of the colours in a colour scheme.
(Format > Slide Design) and click Color Scheme.
The Colour scheme task pane will appear
To create a colour scheme for a slide or presentation:
You can change individual colours in a scheme by selecting the custom tab.

Apply - Applies the current colour scheme to the selected slides. The custom colour scheme will also be saved to the presentation for future use.
Preview -
Add as Standard Scheme - Saves the colour scheme to the presentation for future use. This is a little redundant as the Apply button does this by default.

Click the colour box you want to change
Select Change Color button
Click one of the colours and click the Change Color button.
This will display the familiar Colour dialog box allowing you to choose any colour.
repeat for all the colours you want to change

Which tab is displayed by default depends on the current selection.
If the current selection is a custom colour then the Custom tab will be displayed.
If the current selection is a standard colour then the Standard tab will be displayed.

click on the standard tab of the colour scheme dialog box
click on the button that approximates the shading of a colour scheme you want

Choosing your Colours

to apply the new colour only to the current slide click apply
to apply it to all the slides click apply to all

The standard tab displays 127 of the most common colours plus black, white and grey.

If you want to use a colour that is not displayed on the standard tab you can use the Custom tab to define the exact colour.

Saving the Colour Scheme

The colour scheme will actually get saved to the current presentation even if you don't press the "Add as standard scheme".
This is a known bug in PowerPoint 2003.

to save your colour scheme click "add as standard scheme"
Once you have selected the colours select Apply.

Important

You can use the Slide Master to change the colour scheme used for all the slides in a presentation
Try to avoid using colours that clash with each other.