While column families can be configured to keep deleted cells (allowing time range queries to still retrieve those cells), deletes are still somewhat unique in that they are irreversible operations. Once a delete has been issued on a cell, the only way to "undelete" it is to rewrite the data with a timestamp newer than the delete.
The idea here is to add an "undelete" operation, that would make it possible to cancel a previous delete. An undelete operation will be similar to a delete, in that it will be written as a marker ("tombstone" doesn't seem like the right word). The undelete marker, however, will sort prior to a delete marker, canceling the effect of any following delete.
In the absence of a column family configured to KEEP_DELETED_CELLS, we can't be sure if a prior delete marker and the effected cells have already been garbage collected. In this case (column family not configured with KEEP_DELETED_CELLS) it may be necessary for the server to reject undelete operations to avoid creating the appearance of a client contact for undeletes that can't reliably be honored.
I think there are additional subtleties of the implementation to be worked out, but I'm also interested in a broader discussion of interest in this capability.