How to refresh F-Curve colors via python?
I think that the fcurves colors are calculated when the graph editor tries to read their value for the first time, so you may have to do that yourself :

for action in D.actions :    
    for fcurve in action.fcurves :
        index = fcurve.array_index

        if fcurve.color_mode == 'AUTO_RGB':
            h = float(1.0)/3.0        
        #I don't have the right formula for rainbow 
        elif fcurve.color_mode == 'AUTO_RAINBOW': 
            h = float(1.0)/4.0  

        fcurve.color.hsv = (index*h, 1, 1)