CSS A and NS records can be 63 characters.
http://www.cisco.com/en/US/customer/products/hw/contnetw/ps789/products_configuration_guide_chapter09186a0080176f52.html
If a valid domain name is issued by a legal authority, it should be able to be used without issue.
Also note that in your example the domain name (common name) is mylongdomainname.com. The www is not necessary as that just points to a sub-function/service within the target domain.
And lastly, I believe you're allowed 128 characters to associate the common name in the certificate. Are they chewing up 90+ and leaving you some subset?
You may want to chat with your technology provider and inquire why they believe limits are being hit and what parts/pieces are breaking.