Jomni, the answer is no -- with an asterisk.
When formatting a cell, you can only pick from the 40 colors that appear (in
Excel 2003 at least) on the color palette. But -- and here's the asterisk --
you can modify that color palette at any time (except when you're actually
using it).
To change Excel's available colors, pull down the Tools menu and select
Options > Color > Modify.