Fix Product Sorting Issues in Magento 1.8

Ok, I try to explain my solution, I give here most important points, but you should have some experiences like magento layouts, blocks, create custom module.
1. Create attribute which you assumed in your question.
2. Configure your products attaching them to particular category and attribute value created above.
3. Create custom block given in example (/app/code/local/Some/Module/Block/Catalog/Navigation.php):

class Some_Module_Block_Catalog_Navigation extends Mage_Core_Block_Template
{
    protected $_attributeCode = 'item_branch';

    /**
     * @return Mage_Catalog_Model_Resource_Eav_Attribute
     */
    public function getAttribute()
    {
        $attribute = Mage::getModel('catalog/resource_eav_attribute')
            ->loadByCode(Mage_Catalog_Model_Product::ENTITY, $this->_attributeCode);
        return $attribute;
    }

    protected function _construct()
    {
        $this->addData(array(
            'cache_lifetime' => false,
            'cache_tags'     => array(Mage_Catalog_Model_Category::CACHE_TAG),
        ));
    }

    public function getCacheKeyInfo()
    {
        $shortCacheId = array(
            'CATALOG_NAVIGATION',
            Mage::app()->getStore()->getId(),
            Mage::getDesign()->getPackageName(),
            Mage::getDesign()->getTheme('template'),
            'template' => $this->getTemplate(),
            'name'     => $this->getNameInLayout(),
            $this->_attributeCode
        );

        return $shortCacheId;
    }

    public function getCategoryUrl($category)
    {
        if ($category instanceof Mage_Catalog_Model_Category) {
            $url = $category->getUrl();
        } else {
            $url = $this->_getCategoryInstance()
                ->setData($category->getData())
                ->getUrl();
        }

        return $url;
    }

    public function getTree()
    {
        $attributeId = $this->getAttribute()->getId();
        $websiteId   = Mage::app()->getWebsite()->getId();

        $resource   = new Mage_Catalog_Model_Resource_Setup('core_setup');

        $categories = Mage::getModel('catalog/category')->getCollection();

        $categories
            ->addFieldToSelect(array('category_id' => 'entity_id', 'parent_id'))
            ->getSelect()
            ->join(array('cp' => $resource->getTable('catalog_category_product')), 'cp.category_id=main_table.entity_id', 'product_id')
            ->join(array('pw' => $resource->getTable('catalog_product_website')), "pw.product_id=cp.product_id AND  pw.website_id = $websiteId", 'website_id')
            ->join(array('av' => $resource->getTable('catalog_product_entity_int')), "av.entity_id=pw.product_id AND  av.attribute_id = $attributeId", array('option_id' => 'value'))
            ->join(array('ov' => $resource->getTable('eav_attribute_option_value')), 'ov.option_id=av.`value` AND  ov.store_id = 0', array('option_value' => 'value'))
            ->order(array('option_value', 'category_id'));

        $query = $categories->getSelectSql(true);

        $data = $resource->getConnection()->fetchAll($query);
        $tree = array();

        foreach ($data as $row) {
            $optionValue = $row['option_value'];
            if (!isset($tree[$optionValue])) {
                $tree[$optionValue] = array(
                    'label'      => $optionValue,
                    'categories' => array()
                );
            }
            $parentCategory = $row['parent_id'];
            if (!isset($tree[$optionValue]['categories'][$parentCategory])) {
                $tree[$optionValue]['categories'][$parentCategory] = array(
                    'category_id'    => $parentCategory,
                    'sub_categories' => array(),
                );
            }
            $categoryId = $row['category_id'];
            $tree[$optionValue]['categories'][$parentCategory]['sub_categories'][$categoryId] = $categoryId;
        }

        return $tree;
    }
} 

I created this block to achieve caching of my custom category navigation, because of to build this navigation it is required to load extra data from db. But you can use tree build logic in code given above without using block.

4.Add this navigation to frontend using local.xml layout (/app/design/frontend/default/default/layout/local.xml):

<?xml version="1.0"?>
<layout version="0.1.0">
    <catalog_category_default translate="label">
        <reference name="left">
            <block type="some_module/catalog_navigation" name="catalog.leftnav" before="currency"
                   template="catalog/navigation/myleft.phtml"/>
        </reference>
    </catalog_category_default>

    <catalog_category_layered translate="label">
        <reference name="left">
            <block type="some_module/catalog_navigation" name="catalog.myleft"
                   template="catalog/navigation/myleft.phtml"/>
        </reference>
    </catalog_category_layered>
</layout> 

5.Create navigation block template (/app/design/frontend/default/default/template/catalog/navigation/myleft.phtml):

<?php /* @var $this Some_Module_Block_Catalog_Navigation */ ?>
<?php $tree = $this->getTree(); ?>
<?php $categories = Mage::getModel('catalog/category')->getCollection()->addAttributeToSelect('name'); ?>
<?php $_count = count($tree) ?>
<?php if ($_count): ?>
    <div class="block block-layered-nav">
        <div class="block-title">
            <strong><span><?php echo $this->__('Browse By ') . $this->getAttribute()->getFrontendLabel() ?></span></strong>
        </div>
        <div class="block-content">
            <?php foreach ($tree as $label => $optionCategory): ?>
                <div>
                    <h5><?php echo $label ?></h5>
                    <ul>
                        <?php foreach ($optionCategory['categories'] as $parent): ?>
                            <?php $_category = $categories->getItemById($parent['category_id']) ?>
                            <li>
                                <a href="<?php echo $this->getCategoryUrl($_category) ?>"><?php echo $this->htmlEscape($_category->getName()) ?></a>
                                <ul>
                                    <?php foreach ($parent['sub_categories'] as $categoryId): ?>
                                        <?php $_category = $categories->getItemById($categoryId) ?>
                                        <li>
                                            --<a href="<?php echo $this->getCategoryUrl($_category) ?>"><?php echo $this->htmlEscape($_category->getName()) ?></a>
                                        </li>
                                    <?php endforeach ?>
                                </ul>
                            </li>
                        <?php endforeach ?>
                    </ul>
                </div>
            <?php endforeach; ?>
        </div>
    </div>
<?php endif; ?>

6.You can fix design of this menu adding some css classes and rules as you want.

By the way your attribute type should be select. Try to understand the logic and adjust it to your store, this gives me perfect result, maybe it not works via copy/paste without understanding and adjusting the code. See my result:

P.S: maybe this solution has some bugs or issues which I didn't sense, comments will be appreciated.

Short answer: The sorting doesn't work for Yes/No attributes.

Long Answer:
The problem:

When calling addAttributeToSort on a product collection, if the attribute has a source model then Magento calls addValueSortToCollection from that source model to sort the products.
The Yes/No attributes use the source model Mage_Eav_Model_Entity_Attribute_Source_Boolean that does not implement the method addValueSortToCollection For this model the method just returns $this without processing the collection.

A possible solution:
You can rewrite the Mage_Eav_Model_Entity_Attribute_Source_Boolean and add your addValueSortToCollection method. It should basically be the same code as it is in the class Mage_Catalog_Model_Product_Visibility or Mage_Catalog_Model_Product_Status (not entirely sure about this) which is:

public function addValueSortToCollection($collection, $dir = 'asc')
{
    $attributeCode  = $this->getAttribute()->getAttributeCode();
    $attributeId    = $this->getAttribute()->getId();
    $attributeTable = $this->getAttribute()->getBackend()->getTable();

    if ($this->getAttribute()->isScopeGlobal()) {
        $tableName = $attributeCode . '_t';
        $collection->getSelect()
            ->joinLeft(
                array($tableName => $attributeTable),
                "e.entity_id={$tableName}.entity_id"
                    . " AND {$tableName}.attribute_id='{$attributeId}'"
                    . " AND {$tableName}.store_id='0'",
                array());
        $valueExpr = $tableName . '.value';
    }
    else {
        $valueTable1 = $attributeCode . '_t1';
        $valueTable2 = $attributeCode . '_t2';
        $collection->getSelect()
            ->joinLeft(
                array($valueTable1 => $attributeTable),
                "e.entity_id={$valueTable1}.entity_id"
                    . " AND {$valueTable1}.attribute_id='{$attributeId}'"
                    . " AND {$valueTable1}.store_id='0'",
                array())
            ->joinLeft(
                array($valueTable2 => $attributeTable),
                "e.entity_id={$valueTable2}.entity_id"
                    . " AND {$valueTable2}.attribute_id='{$attributeId}'"
                    . " AND {$valueTable2}.store_id='{$collection->getStoreId()}'",
                array()
            );
            $valueExpr = $collection->getConnection()->getCheckSql(
                $valueTable2 . '.value_id > 0',
                $valueTable2 . '.value',
                $valueTable1 . '.value'
            );
    }

    $collection->getSelect()->order($valueExpr . ' ' . $dir);
    return $this;
}

Explanation provided here also for a similar issue