A const reference in C++ is like an interface that doesn't have any mutating methods, except that all the methods of the interface have the same names and signatures as the original, and I don't have to actually type out a separate interface definition, I just choose which methods I want to appear in both the immutable and mutable interfaces by appending a "const" to their signatures (bonus: if the implementation for the const version is different, I can overload it.)
Sure, C++'s const has tons of problems, but it seems like the Java and C# designers looked at it and said "const is probably more trouble than it's worth so let's not bother." Which is a fair assessment, I guess.
The point isn't the loss of "const", it's that the only access you do have to a class-type object in C++/Java/C# is via its interface.
If you hold all of an object's current state in private data members, then the only way you can change that state -- even if you can see the object and it isn't const -- is via the interface functions provided. If as class designer you just happen not to provide any interface functions that mutate the object (no set_whatever() calls, no assignment operators, etc.) then your object becomes immutable by implication.
The finer control the GP mentioned probably refers to the way you can also choose to permit certain specific types of mutation, by providing a limited set of functionality in the interface rather than direct access to the underlying values.
Sure, consider this: http://pastebin.com/H3c83X1K
Here we can give a client a write-only interface to the Mailbox, or one of two readonly (i.e. "const") interfaces that each have access to a subset of Mailbox's "const" methods.
Java is meant to be "C++ without the sharp bits", and removed this feature (and a host of other stuff); I imagine the fact that arrays are not "OO" enough has also something to do with it. C# is meant to be "Java done right/the MS way", and followed suit.
I see how const_iterator can be a stumbling block, but I'd like to hear your reason for why it doesn't work well. It is different than iterator, since const_iterator accesses const values (by convention).