Hello,
Won't take credit for finding this as somebody else gave me the idea, but I haven't seen the solution posted anywhere in the forums and several people have asked.
To create a multi-line legend label, you simply need to add \r\n into the label where you want the second (and third, fourth, etc) line to start. For example:
"This is my\r\nmulti-line label" will display in the legend label as
This is my
multi-line label
I know that you will be able to write multi-line legend descriptions from python script in 10.1, but with this trick, you will be able to write both labels and descriptions on multiple lines.
Hope that helps somebody.