I've never encountered difficulty in cloning data structures in Perl, usually I just use Clone or sometimes Storable's freeze + thaw (the later does not yet support cloning Regexp objects out of the box).
However, I like Data::Clone for its speed! It's several times faster than Clone or freeze+thaw. So hats up. Planning to use Data::Clone in future projects.
Now if we can convince Goro to write a fast serializer/deserializer with compact output (essentially, a faster version of Storable), that would be even nicer :-)