Creating dynamic, shaded backgrounds for animations
Here's my solution. It provides for altering the Horizon Color and the Zenith Color, and assumes you are using the Blender Internal render engine.

It also allows you to provide a list of frame numbers and colour values for setting up multiple keyframes.

Also, the default interpolation type for animation curves is Bezier which would give you smooth transitions between colors. Because you want abrupt color changes I added code to alter the interpolation mode to Constant for the new animation curves.

import bpy

scn = bpy.context.scene
world = bpy.context.scene.world
world.use_sky_blend = True

#bgColorList[frameNumber, horizonColor, zenithColor)
bgColorList = [
[1,     (1.0, 1.0, 1.0),    (0.8, 0.8, 0.8)   ],
[15,    (0.8, 0.8, 0.8),    (0.8, 0.8, 0.8)   ],
[30,    (0.5, 0.5, 0.5),    (0.2, 0.2, 0.2)   ],
[45,    (0.8, 0.8, 0.8),    (0.8, 0.8, 0.8)   ],
[60,    (1.0, 1.0, 1.0),    (0.8, 0.8, 0.8)   ],
[75,    (0.5, 0.5, 0.5),    (0.2, 0.2, 0.2)   ]
]

#set up all keyframes for background colors             
for bg in bgColorList:
    frame = bg[0]
    hColor = bg[1]
    zColor = bg[2]

    scn.frame_current = frame
    world.horizon_color = hColor
    world.zenith_color = zColor
    world.keyframe_insert("zenith_color")
    world.keyframe_insert("horizon_color")


#modify the interploation mode of the animationt curve to be consant for immediate changes on frame entry
for f in world.animation_data.action.fcurves:
    if f.data_path == "zenith_color" or f.data_path == "horizon_color":
        for kf in f.keyframe_points:
            kf.interpolation = 'CONSTANT'