How can we increase Common-Name attribute maximum length?

No you cannot* change the CN limit to be larger than 64. References include MSDN, MSDN again, and a Microsoft group thread.

(*Okay, yes you can hack around LDAP in ADSI edit and find the CN attribute and increase it. This will do Evil Things as CNs are expected to be a certain length limit that will fit in the overall 256 character display name limit and also break certificates if you ever have a PKI because certificates are expected to never have CN attribute longer than 64 characters as per RFC 5280)

I suspect you could change the AD schema. Every directory schema object has a maximum, which in the case of this would be the maximum length of the string. However, I strongly recommend that you don't change the existing schema objects, as it will complicate things like upgrades later, and it's possible that at least some program logic is predicated upon the default maxima.

In this case, the thing you're looking for is the Common-Name attribute (cn in LDAP format), and you can change the Range-Upper property on that to whatever value. This will affect the maximum length for this on all classes (users too, etc.), because in LDAP attributes are associated with bot not owned by classes. However, don't do this because lots of things will break. The limit is there for a reason and I can't even count the number of things that might become potential issues.