Have a look at how it's been done in the layered navigation:

the responsible method is Mage_Catalog_Model_Resource_Layer_Filter_Attribute::getCount():

/**
 * Retrieve array with products counts per attribute option
 *
 * @param Mage_Catalog_Model_Layer_Filter_Attribute $filter
 * @return array
 */
public function getCount($filter)
{
    // clone select from collection with filters
    $select = clone $filter->getLayer()->getProductCollection()->getSelect();
    // reset columns, order and limitation conditions
    $select->reset(Zend_Db_Select::COLUMNS);
    $select->reset(Zend_Db_Select::ORDER);
    $select->reset(Zend_Db_Select::LIMIT_COUNT);
    $select->reset(Zend_Db_Select::LIMIT_OFFSET);

    $connection = $this->_getReadAdapter();
    $attribute  = $filter->getAttributeModel();
    $tableAlias = sprintf('%s_idx', $attribute->getAttributeCode());
    $conditions = array(
        "{$tableAlias}.entity_id = e.entity_id",
        $connection->quoteInto("{$tableAlias}.attribute_id = ?", $attribute->getAttributeId()),
        $connection->quoteInto("{$tableAlias}.store_id = ?", $filter->getStoreId()),
    );

    $select
        ->join(
            array($tableAlias => $this->getMainTable()),
            join(' AND ', $conditions),
            array('value', 'count' => new Zend_Db_Expr("COUNT({$tableAlias}.entity_id)")))
        ->group("{$tableAlias}.value");

    return $connection->fetchPairs($select);
}

Unfortunately you can't use that straight away with any collection because it's too tightly coupled to the filter model, which again doesn't handle arbitrary product collections.

So your best option is probably to copy what you need from there into an own resource model like this (untested):

class Your_Extension_Model_Resource_Attribute extends Mage_Core_Model_Resource_Db_Abstract
{
    public function getCount($productCollection, $attributeCode, $storeId)
    {
        // clone select from collection with filters

        //----------------------------------------------------------------
        $select = clone $productCollection->getSelect();
        //----------------------------------------------------------------

        // reset columns, order and limitation conditions
        $select->reset(Zend_Db_Select::COLUMNS);
        $select->reset(Zend_Db_Select::ORDER);
        $select->reset(Zend_Db_Select::LIMIT_COUNT);
        $select->reset(Zend_Db_Select::LIMIT_OFFSET);

        $connection = $this->_getReadAdapter();

        //----------------------------------------------------------------
        $attribute  = Mage::getModel('eav/entity_attribute')->loadByCode($attributeCode);
        //----------------------------------------------------------------

        $tableAlias = sprintf('%s_idx', $attribute->getAttributeCode());
        $conditions = array(
            "{$tableAlias}.entity_id = e.entity_id",
            $connection->quoteInto("{$tableAlias}.attribute_id = ?", $attribute->getAttributeId()),

        //----------------------------------------------------------------
            $connection->quoteInto("{$tableAlias}.store_id = ?", $storeId),
        //----------------------------------------------------------------

        );

        $select
            ->join(
                array($tableAlias => $this->getMainTable()),
                join(' AND ', $conditions),
                array('value', 'count' => new Zend_Db_Expr("COUNT({$tableAlias}.entity_id)")))
            ->group("{$tableAlias}.value");

        return $connection->fetchPairs($select);
    }

}

And then call it like

$options = Mage::getResourceModel('your_extension/attribute')
    ->getCount($collection, 'color', Mage::app()->getStore()->getId());

$options will be an array with the values as key and number of occurances as value. Filtering out the 0's should not be a problem from there.