When you run with "Cover as" the instrumentation will add extra code in your method (to report when each line/expression is hit within the tests). If your message is already very large, that extra instrumentation may well be pushing it over the 64K limit.
It doesn't mean there's anything wrong with the code - it just means you won't be able to use it in coverage tests :(