Because immutable collections absolutely require sharing to be usable. Otherwise, every single operation drops a whole other list into the heap somewhere. Languages that are entirely immutable, like Haskell, generate astonishing amounts of garbage without aggressive optimizations and sharing. Having collection that's only usable with <50 elements is not worth putting in the standard library.
Further more, immutable collections often have fundamentally different implementations than their mutable counterparts. Consider for example ArrayList, an efficient immutable ArrayList wouldn't be an array at all! It should be implemented with a balanced tree with a large branching factor, Clojure uses 32 IIRC. Making mutable collections be "immutable" by just adding a functional update is a performance bug just as much as a memory leak is.
Furthermore, sharing isn't viable in Java. Java provides too many unrestricted hooks to mutability and reference equality to make sharing "just an optimization". It'd probably irk you a bit if you could modify an element in a list, and realize you just modified an element in the other 20 versions of that list you had.
This also rules out huge classes of very vital optimizations for efficient immutability, sharing, stream fusion, you name it, mutability breaks it. (That'd make a good slogan for FP evangelists)
Best Answer
An immutable class is immutable, as in, it is not mutable. You cannot change it. If you have x::String, you can be absolutely 100% certain that x will never ever change ever (or at least, if it does, people are abusing the flexibility of your language and you have every right to tell them where to go).
A mutable class is not immutable. You can change it, other people can change it, and you can't rely on it being the same. It could be changed in another thread, you can't even be sure of it being in the same state from line to line unless you have good locking.
The ability to alter the state of the object is the key concept, but the story doesn't end there. You might want to choose an immutable class in a threaded environment, because now you don't need to worry about locking, because nobody can write to it anyway. You might want to choose immutable objects in a large system, because you can't be certain that nobody else has a handle on that input parameter and won't change it out from under you the first chance they get. You might want to choose immutable objects because they make reasoning about the behaviour of your code in small units possible--as in, if everything about a function relies on immutable data, you can look at that function in isolation, guaranteed.
There are performance impacts, but it's not all one way. Immutable objects enable a lot of optimisations you just can't do on mutable data, like aggressively sharing memory (because hey, it can't change) or more aggressive inlining. Mutable data tends to get performance increases when you need to make a lot of changes to blocks of memory.
If you're interested in seeing somewhere where immutability really shines, take a look at a language like Haskell, which was designed from the ground up for immutability, enabling language-level support for things like laziness and a lot of optimisation.