How can I replace a material from Python?
Ok from the above I noticed there are possibly 2 approaches to the same problem.

1) is iterate through the list of available materials linked as data and replace the material. This will not work if materials are linked by Object.

Sample code below:

import bpy

def replace_material(object,old_material,new_material):
    """
    replace a material in blender.
    params:
        object - object for which we are replacing the material
        old_material - The old material name as a string
        new_material - The new material name as a string
    """
    ob = object
    om = bpy.data.materials[old_material]
    nm = bpy.data.materials[new_material]
    materialnum = len(ob.data.materials)

    for i in range(0,materialnum):
        # test if the old material is in the list of used materials and replace it
        print ("running ", i)
        if ob.data.materials[i] == om:
            print ("match found", ob.data.materials[i])
            ob.data.materials[i] = nm


2) Iterate over material slots and replace the material in the slot of the object. This as batFINGER pointed out is a solution wherein whether the material is linked to the Object or Data is irrelevant and hence probably a better solution.

import bpy

def replace_material(object,old_material,new_material):
    """
    replace a material in blender.
    params:
        object - object for which we are replacing the material
        old_material - The old material name as a string
        new_material - The new material name as a string
    """
    ob = object
    om = bpy.data.materials[old_material]
    nm = bpy.data.materials[new_material]
    # Iterate over the material slots and replace the material
    for s in ob.material_slots:
        if s.material.name == old_material:
            s.material = nm


Notes:

1) The above samples do not do any error handling the script will just fail if the materials do not already exists. I wanted this kind of behavior.

2) For brevity sake I have posted only definition of the functions themselves this function can be used for a single object or along with looping to work with several objects. An example of such is shown in the main() function in the question.

Usage:
Suppose you have an object named "Bottle" 2 materials "Red paint" "Blue rubber"
and you want to replace the material "Red Paint" with "Blue rubber"

then you would use:

obj = bpy.data.objects["Bottle"]
replace_material(obj,"Red paint","Blue rubber")