Set style of legend items to user style and tests 'Override default patch' property. Mxd.save() seems like the key here.

legend_style.py

import arcpy

mxd = arcpy.mapping.MapDocument("./Legend.mxd")
df = arcpy.mapping.ListDataFrames(mxd)[0]

#Setup Legend
legend = arcpy.mapping.ListLayoutElements(mxd, "LEGEND_ELEMENT")[0]
styleItems = arcpy.mapping.ListStyleItems("USER_STYLE", "Legend Items")
for styleItem in styleItems:
    if styleItem.itemName == "PATCH_Single":
        legendStyle = styleItem

for lyr in legend.listLegendItemLayers():
    legend.updateItem(lyr, legendStyle)

mxd.save()

print "done"