Well, I have to disagree with David M. Kean about using copy constructors. Not that I think copy constructors are bad (they aren't), but his argument fails on two grounds.
1. A copy constructor has the exact same issue talked about by Jonathan. There's no way to know if the copy constructor is going to make a deep or shallow copy.
2. A copy constructor can not be used polymorphically, which is the whole point in using a "Clone" method in OO languages.
Personally, I don't think throwing ICloneable out is appropriate. Me, I always assume this does a shallow copy (which usually won't cause issues even if a deep copy is made), and if I must have a deep copy I use a custom IDeepCloneable interface.
The design of this interface was flawed, since it didn't specify the type of copy that would be done, but the concept is still useful and even necessary at times.