The main (only?) down side of immutable object is the fact that they make it difficult to update the data in your program. This should not be a surprise. After all, if they are immutable then it only makes sense that they will not encourage mutations.
Here is the general description of the problem: if x is an immutable object and x.f == y, and you want x.f to point at z, then you can't just set x.y to z. You need to create a new object, x', that is identical to x in all aspects except that x'.f == z. You then need to find all references to x and reroute them to x'.
In certain cases (such as: many object holding references to x) this rerouting may be quite hard and error prone. Also, if the objects pointing at x are immutable themselves, then further updates need to be carried out across your data structure. These difficulties are the reason why most C/C++/Java/C# folks tend to prefer designs with mutable objects, despite the benefits of immutability.
Side note: functional languages usually offer powerful pattern matching mechanisms that simplify the process of updating (immutable) data structures.
Anyway, even in cases where correctly rerouting references is not that bigger problem, developers are sometimes reluctant to use immutability due to performance issues. The argument goes as follows: If I make this class immutable, I will have to allocate a new object every time I update one of the fields. This extra allocation will slow down my program.
This argument is, by and large, incorrect.
Reason #1. Most of the code you're writing will not affect the performance of your program. There is no point in optimizing your code prematurely.
Reason #2. Mutable objects lead to defensive getters/setters. That is, If a method returns a field pointing at a mutable object it usually needs to create a copy of it to prevent the caller from breaking the invariants of the class. This means that an object will be duplicated even if the caller just wants to read its content. Given that reads are more frequent than writes we actually have that immutable objects yield faster programs simply because they do not imply object copying with every get/set operation.
I experienced this effect a few years ago when I had to optimize CPU-intensive code that dealt with queries over in-memory tables. The profiler indicated that most of the time my program was busy duplicating rows of these tables which, usually, were not mutated at all. Switching into an immutable design resulted in a significant performance boost.
Still not convinced? Maybe this will help you. When Josh Bloch discusses API design decisions that create performance problems, he gives as an example Java's Dimension class which is---wait for it---mutable. Specifically, each call to Component.getSize() must allocate a new Dimension object which leads to numerous needless allocations. Further details are given in Josh's excellent lecture, How to Design a Good API & Why it Matters (Immutability of class Dimension is discussed ~ 32 min. into the talk).