I was having trouble, but it was not too much trouble, of getting my iCal colors to sync with my iPhone. I finally found the answer if you use MobileMe accounts. The last comment tells you how to do it properly.
Bottom line: Go to your MobileMe account, click on any calendar, select the “starred” button that has the menu “Calendar Info,” select the color you want for the calendar, and then click the OK button.
Works for me now.