Most of the color sims came online before Second Life's initial launch, with two new sims being added for the first Burning Life event, and the top rows coming a bit later. Between June 18th and June 23rd of 2003, most likely, is when the first color sims came online.
The first color sims to come online were the themed sims around the "new" or "backup" welcome area. As Eggy Lippmann was in Americana, he had access to an island made up of Blue (Americana) and Gray (Kazenojin) long before they were visible to the rest of the world.
The other themes were Wiz World, a theme park in Mocha, Little Tokyo, a medieval japanese village in Sage, and Eggy is told, Rose was supposed to be a themed sim as well, but it failed even faster than Wiz World. Eggy forgot what it was about, but surely some info on it will be in the forums.