Use allow qty below 0 on the product and add
<?php $product_inventory = Mage::getModel('cataloginventory/stock_item')->loadByProduct($_product) ?>
<?php if($product_inventory->getQty() <= 0 && ($product_inventory->getBackorders() == 1 || $product_inventory->getBackorders() == 2)): ?>
<p class="choseyourclass"><?php echo $this->__('Availability:') ?><span><?php echo $this->__('Back Ordered') ?></span></p>
Before the first if and make the first if an elseif.
You could also do it with an attribute and set this on inventory update with the above condition, this would decrease load avoiding the cataloginventory model call. You would have to set the attribute manual at first tough (do a massupdate trough the Products grid or use import/export).
(For example observe cataloginventory_stock_item_save_after (I think there will be more needed))
There might be a typo or something in the example as I just typed it by heart.