Hmm, well I guess while we're still on the topic, if colors do happen to be an issue (and it's been a while since I played, so I don't remember all the colors currently in use), here's a suggestion:
The civs would have dibs some form of red are:
-Russia
-Japan
-Ottoman Empire
-England
-China
-Poland
-Vietnam
-Byzantine Empire? (as brought up)
Also, imo, there are three really distinct shades of red: light red, red, and dark red (maroon), so that can help as well.
So here's what I'd think:
-Russia: Russia deserves pure red the most, for reasons I've mentioned before.
-Turkey: The Ottomans and Turkey have always been associated with red as well (sometimes green because of the caliphate), and as the Ottoman flag is darker red, a shade of red slightly darker than pure red (as in the Ottoman flag) would work.
-Poland: Poland can have deep dark red.
-China: Yellow. Although red is the color of the Han Chinese (I was wrong before), yellow was the color of the Qing Empire (not a good representation since it was a Manchu dynasty, but still...), also a symbol of the emperor, and is the other color of the Chinese flag.
-Vietnam: Light yellow
-Japan: Pink. To avoid the whole red/white/yellow struggle, pink would be a good color to represent Japan because of their strong national symbolic association with the cherry blossom.
-England: Light red. Red is often associated with England/Britain because of the Redcoats and St. George's Cross. The lighter shade of red also brings it closer to its second main color, white.
Though that kind of leaves white open (the two strongest contenders for that would be England and Japan), but that can be tossed around I guess. if it's possible, Byzantium could be gold then, if it's so important.