Really, I think most people are confused by the boundary between interface and implementation.
It's possible to have a mutable string interface built on an immutable string implementation. Just add indirection! We can get the best of both worlds: immutability of actual strings optimizes comparison of strings, while the pseudo-mutable strings allow you to pass data across functions by a method other than returning a value (i.e. mutating the string).
That's a good point. However, it leaves open the question of what "a new string" creates. One can build either one on top of something else (e.g. immutable strings on top of symbols [though one could argue that that's what symbols are, I suppose]), so the real question (it seems to me) is what the default should be.
This isn't so much code is spec, though: Arc only has mutable strings and symbols. You could consider symbols immutable strings, but they exist to fill a different niche. If mutable and immutable strings were created, then the code-spec would have to deal with this; I think it would be capable of doing so.
I'm not so concerned with how Lisps represent symbols and (mutable) strings as long as (1) my strings can be modified, and (2) comparing symbols takes constant time. If it's the Lisp interpreter protecting the string-representing-the-symbol, so be it; that doesn't affect me as a Lisp programmer.
: Although if I recall, Ruby 2.0 will make its Symbols "frozen" (immutabilified) Strings, thus allowing things like regex matching on Symbols. This might be an interesting approach...