Never fear. Thanks to Palanikumar, we can override the core files.

Firstly, copy Breadcrumb.php from

app/code/core/Mage/Page/Block/Html

to

app/code/local/Mage/Page/Block/Html

And then replace the function _toHtml() (it should be easy to locate)

with the following updated function.

protected function _toHtml() {             

       $cat_id = "";

       if (Mage::registry('current_product')) {
          $product_id = Mage::registry('current_product')->getId();
          $obj = Mage::getModel('catalog/product');
          $_product = $obj->load($product_id); // Enter your Product Id in $product_id

          if ($product_id) {
             $categoryIds = $_product->getCategoryIds();
             $cat_id = $categoryIds[0];
          }

          $category = Mage::getModel('catalog/category')->load($cat_id);
          $cat_name = $category->getName();
          $cat_url =  $this->getBaseUrl().$category->getUrlPath();
       }

       if (is_array($this->_crumbs)) {
          reset($this->_crumbs);
          $this->_crumbs[key($this->_crumbs)]['first'] = true;
          end($this->_crumbs);
          $this->_crumbs[key($this->_crumbs)]['last'] = true;
       }

       if($cat_id) {
          $this->_crumbs['category'.$cat_id] = array('label'=>$cat_name, 'title'=>'', 'link'=>$cat_url,'first'=>'','last'=>'','readonly'=>'');
          ksort($this->_crumbs);
          $home = $this->_crumbs['home'];
          unset($this->_crumbs['home']);
          array_unshift($this->_crumbs,$home);
       }

       $this->assign('crumbs', $this->_crumbs);
       return parent::_toHtml();
    }

BOOM!