Others have made good summaries of why you want to use immutable objects, so I won't list the reasons why they are good again. In short it all comes down to easier and safer code. It also allows for performance optimizations that are not possible without (hashcode caching and String.intern() to start with, but even more in distributed computing).
What I would like to see is to go a step further and introduce value types. With this I mean types of objects that are not only immutable but are treated as values in all regards, which most importantly adds the notion that they should use value equality, i.e. two instances of a type are considered the same whenever all members are the same. The members of value objects are restricted to other value types.
Some existing languages use this notion, most noticably C# (in form of structs and enums) or Lava (a language unrelated to Java). Java itself has a number of value types such as all primitives and some object classes such as String. But the notion of a value type is not well established and in fact primitives are treated quite differently to String, which in turn has its own specific hacks in the Java compiler.
Instead of having primitives and targetted optimizations for specific classes such as String Java should have a proper notion of value types that are:
- reference only other value types
- use value identity
So my fictional version of Java that I call Java3k would have value types so we:
- can write safer code
- don't have to worry about writing hashCode() and equals(..)
- can rely on a lot of performance optimization by the compiler
- can forget about primitives (and all the boxing/unboxing annoyances)
- have an easier time writing multi-threaded and distributed applications
I think a separation of your types into value types and the rest (which can then further be separated) is a very valuable approach and personally I prefer taking it as far as I can in the sense that I try to make as many types value types as I can and disallow value identity outside that group. It makes for much cleaner code even if you don't have language support.
The other effect it has is that it leads you towards writing more and more code as pure functions. Instead of mutating state on objects you let them create new objects without changing themselves. The substring method on Java's String class is such an example: it doesn't change the String instance it is called upon but creates a new object. That might make it confusing for beginners, but it means that it will never cause unwanted side effects (and the part of being confusing is only since Java let's you ignore return values, which is a feature that falls under the category of Pretty Bad Ideas). And not having side effects is extremely valuable -- similar to many other good ideas you have to get used to it (unless you have been raised on a functional programming language), but once you get the idea you don't want to miss it.
So that is my first feature for my fictious Java3k: explicit value types instead of primitives and mystery hacks for String and the like. It would not only add a lot of value in terms of safer and faster code but also get rid of enough cruft to effectivly reduce the language complexity significantly.
PS: once you have value types you could also add derivation by restriction such as used in XML Schema, but maybe that's a Java4k feature.