How can I use both context and threading?
It will not fully answer your question, but it might point you the right direction. The context which you are grabbing during script execution is not necessarily the 3D View context, which you get for instance when you call it from the Python console. Blenders context changes depending on the situation, that's why it was given that name I guess  :) 

So, if you change your FOR loop to this, the script at least executes:

    for i in range(0, max_range):

        bpy.ops.mesh.primitive_cube_add(radius = 1, location=(0, 0, 1))
        bpy.ops.object.origin_set( type="ORIGIN_CURSOR" )

        # check what attributes the current context offers
        print(dir(bpy.context))

        # now grab a reference to the active object
        ao=bpy.context.scene.objects.active

        ao.scale.x = scale
        ao.scale.y = scale
        ao.scale.z = 5

        bpy.ops.object.transform_apply(location = False, rotation = False, scale = True)
        ao.location = (((i*scale*2)+(i*space))-(((max_range*scale*2)+(max_range*space)))/2,0,0) 


I've added this line on purpose:

    print(dir(bpy.context))


console output:

['__doc__', '__module__', '__slots__', 'area', 'bl_rna', 
'blend_data', 'copy', 'mode', 'region', 'region_data',  
'rna_type', 'scene', 'screen', 'space_data', 'tool_settings', 
'user_preferences', 'window', 'window_manager']


in the console you can this way see what attributes you can access, and one of them is the current scene. so by calling the active object from there, I can access it:

    ao=bpy.context.scene.objects.active


The problem is not solved however. On my machine I get 5 Objects, but only one of them contains a mesh. I can only guess what's happening, I think it is a racing condition. Since each thread calls the active object, and each one creates a new active object, one thread might 'steal' it from the other, thus affecting its location and even object data.

Consider creating the objects you need directly in bpy.data and link them to the scene manually, this way you get a unique reference to the object directly. You'll find guides on how to do this here on this site. Good luck!