In Excel shape objects can be given basically any color independent of
the Excel color palette (56 colors) and independent of the 80 Scheme
colors. This was already possible in Excel versions prior to 2007.

This means you might be able to solve your problem by just assigning a
color value directly to the RGB property of the fill object.
Its a long time since I worked with the colors of shape objects but I
see in my old code that for assigning a color I had to do some
deselecting and selecing again to work with the buil-in Excel dialog
xlDialogEditColor
That might not be neccessary in your case.

Here a short code snippet that shows you how I do change the color of
a shape object. Still works in XL2007
.....
dim NewColor as long
.....
Select Case TypeName(Selection)
Case "Rectangle", "Oval", "TextBox", "Drawing"
On Error GoTo err_hdl
Set shpR = Selection.ShapeRange
On Error GoTo 0
'we can't start the Dialogs(xlDialogEditColor) when a
shape is selected so therefore
' some code to activate the worksheet while we go to the
dialog
ActiveWorkbook.Windows(1).Activate
If ActiveSheet.Type = xlWorksheet Then
shpR.Item(1).TopLeftCell.Select
End If
newColor = PickNewColor(CDbl(colStart), colID, True) ' my
custom function to handle xlDialogEditColor
shpR.Select
With shpR.Fill
.ForeColor.RGB = newColor
End With
end select
.....