How to clone the collection in Magento?
Use of the PHP clone operator, where deep cloning is desired, requires classes which store objects on properties implement a __clone method to copy the objects. If they don't define it, the properties on both instances will reference the same object.
Magento does not implement __clone on it's collection abstracts, and therefore does not support deep cloning as you want it to.
My suggestion is to look for other ways to accomplish what you are wanting to do, as cloning a collection could be pretty expensive.
The example you gave (for instance) could be changed to clone the select, modify it to select a count of the records it would have loaded and then based on that result modify the collection. This would also perform better since you would not be loading a collection and counting it just to determine which one to use.
EDIT: The following demonstrates how to grab a count without loading or actually modifying the collection.
$collection = Mage::getModel(...)->getCollection();
$count = $collection->getSelectCountSql();
$count->where('some where condition');
if ($count->query()->fetchColumn() == 0) {
...
} else {
...
}