I'm not sure what you're doing differently from me. I have no trouble adding my own color scheme to the ColorData database in my init.m file. I used ColorData[1]; instead of ColorData[]; to load the built-in database, but I doubt that is significant.

In any case, the data is stored in binary format in the file (at least on a Mac):

$InstallationDirectory/SystemFiles/Kernel/SystemResources/64Bit/DataPaclets/ColorData.mx

Alternatively, you can locate the file with the following:

FileNameJoin[{System`Private`$SystemFileDir, 
   ContextToFileName["DataPaclets`ColorData`"]}] <> "x"

I don't think you can do much with the file though, other than load it and then amend the database. Or get WRI to accept your color schemes as part of the Mma distribution.