I would be very curious to understand the runtime implications of imposing immutability on an Objective-C program. Presumably porting that was a lot of work.
Many Cocoa classes are immutable (NSString, NSDictionary, NSArray). You can use the mutable versions (i.e. NSMutableString, NSMutableDictionary, NSMutableArray) but there's no reason to if the immutable versions are a better fit for clojurem.
If by runtime implications you mean speed, I think it'd be ok. Objective-C makes heavy use of immutable data structures already, and iPhone apps just don't have that much data, anyway.
I haven't looked at the source, but the avoidance of full copy-on-write, laziness and instrumentation of immutable structures when returning from functions that update / assoc them will be non-trivial to get right. Not even to mention software transactional memory Clojure supports at all.
Immutability in general isn't that big of a deal. The problem is that Clojure uses persistent trees for all datastructures, which will trigger alot of retain/release calls. Other than some RC overhead, it should work just fine. A GC would be ideal however.
Using mutable data structures is pretty easy in clojure, I'm going to dig around and see how they handle this.