You'd be amazed what you can do with CAS these days; you can build full lock free implementations of collections, maps and so forth. Hardcore CAS state machine stuff; the kind of thing you wanna reuse from a library :) http://code.google.com/p/jjoost/wiki/LockFreeHashStore
Immutabiliy and persistent collections (as used heavily in clojure et al) are certainly a nice & simple approach to concurrency & avoid lots of problems - they make things much easier to reason about for application programmers. Though for really high performance requirements; immutabiliy seems to add lots of cost onto the garbage collector (as every opteration requires allocating new objects), so CAS tends to be faster - especially for collections.