It took me a while to figure this out but finally thanks to this forum post I did it. I think what was confusing me was you had to get the control and then set the label.
var affectedControl = Xrm.Page.ui.controls.get(fieldname);
var affectedAttribute = Xrm.Page.data.entity.attributes.get(fieldname);
Found a few interesting things with this. First, if your field is required, you lose the red * if you change the label. The field is still required but no *. Also, if you change the label and then in jscript try to change the required level (e.g. Xrm.Page.getAttribute(“new_myfield”).setRequiredLevel(“required”);), you get an error.
Working like a charm