Hi Nick,
It can be done but not efficiently, it would be better to
use numbers for sorting purposes and Conditional Formatting
to supply the color rather than the other way around.
For what you ask see Chip Pearson's
SortByColor -- Sorting by Color
http://www.cpearson.com/excel/SortByColor.htm
if colors came from conditional formatting then use the
same formulas on the page and sort them, though see
bottom of page for C.F. colors.
For some additional comments
Color, Sorting on Color
http://www.mvps.org/dmcritchie/excel/colorsort.htm