Rename a constraint in SQL Server?
After some more digging, I found that it actually has to be in this form:
EXEC sp_rename N'schema.MyIOldConstraint', N'MyNewConstraint', N'OBJECT'
Source
You can rename using sp_rename using @objtype = 'OBJECT'
This works on objects listed in sys.objects which includes constraints