Python - Changing scenes' header color gives fever to CPUs
Why so CPU intensive?

Blender will call that function far more often than you think. Prove to yourself by adding a print statement in the function. that will explain the excessive CPU consumption.  It' s a neat idea but this is not the way to implement it. There are no events that fire off upon scene change, else that would be a great idea for an event handler.

One possible approach

I'm hoping this will anger someone else into giving a better answer :)
An alternative is to code a dedicated menu for switching scenes.. something like this.. (use better class names than these )


this gives a menu of scenes in the current blend
lets you pick one
switches color
switches scene


--

import bpy

class SimpleSceneOperator(bpy.types.Operator):
    """Tooltip"""
    bl_idname = "scene.select_and_color"
    bl_label = "Simple Select Scene and Color"

    scene_name = bpy.props.StringProperty()

    def execute(self, context):
        pref = context.user_preferences
        header_colors = [(1.0, 0.7, 0.7),(0.7, 1.0, 0.7),(0.7, 0.7, 1.0)]

        if self.scene_name == 'Editing table':
            col = 0
        elif self.scene_name.startswith("Tag: "):
            col = 1
        else:
            col = 2

        pref.themes[0].info.space.header = header_colors[col]
        context.window.screen.scene = bpy.data.scenes[self.scene_name]
        return {'FINISHED'}


class CustomMenu(bpy.types.Menu):
    bl_label = "Custom Menu"
    bl_idname = "OBJECT_MT_custom_menu"

    def draw(self, context):
        l = self.layout
        col = l.column()
        col.label(text="pick a scene")

        opname = "scene.select_and_color"

        for sc in bpy.data.scenes:
            col.operator(opname, text=sc.name).scene_name = sc.name


def draw_item(self, context):
    layout = self.layout
    layout.menu(CustomMenu.bl_idname)


def register():
    bpy.utils.register_class(SimpleSceneOperator)
    bpy.utils.register_class(CustomMenu)
    bpy.types.INFO_HT_header.append(draw_item)

def unregister():
    bpy.utils.unregister_class(CustomMenu)
    bpy.utils.unregister_class(SimpleSceneOperator)
    bpy.types.INFO_HT_header.remove(draw_item)

if __name__ == "__main__":
    register()

    # The menu can also be called from scripts
    # bpy.ops.wm.call_menu(name=CustomMenu.bl_idname)


could be triggered from 3dview, if you assign a shortcut to it, else the current code adds a menu item to the end of the info header, not ideal but gets the idea across.