So I actually had this working, and without changing anything (or so I thought) it stopped working, and the error I get is just a "this won't work" without even pointing me to a line or anything. Here's the code:
import bpy
#Set parent
bpy.context.scene.objects.active = bpy.data.objects['Armature']
ob= bpy.data.objects['Tuxedo Shirt']
arma = bpy.data.objects['Armature']
bpy.ops.object.select_all(action='DESELECT')
arma.select = True
bpy.context.scene.objects.active = arma
bpy.ops.object.mode_set(mode='EDIT')
parent_bone = 'CC_Base_BoneRoot' # choose the bone name which you want to be the parent
arma.data.edit_bones.active = arma.data.edit_bones[parent_bone]
bpy.ops.object.mode_set(mode='OBJECT')
bpy.ops.object.select_all(action='DESELECT') #deselect all objects
ob.select = True
arma.select = True
bpy.context.scene.objects.active = arma #the active object will be the parent of all selected object
bpy.ops.object.parent_set(type='BONE', keep_transform=True)
I know there are redundancies there, but it was how the code got built and I didn't want to alter anything from what was working. And, yes, those are the right names of the mesh and bone (like I said, it was working just fine -- obviously I must have changed something but I have no idea what it was).