Olá,

1 – Abra o arquivo: app/code/core/Mage/Catalog/Block/Product/List/Toolbar.php
2 – Na linha 232, vai encontrar:

if ($this->getCurrentOrder()) {
 $this->_collection->setOrder($this->getCurrentOrder(), $this->getCurrentDirection());
}
return $this;

 
3 – Acrescente o código e altere da forma que desejar:

if ($this->getCurrentOrder()) {
 if(($this->getCurrentOrder())=='recente'){
  $this->_collection->setOrder('entity_id','desc');
 }else {
  $this->_collection->setOrder($this->getCurrentOrder(),$this->getCurrentDirection());
 }
}
return $this;

 
4 – Agora na linha 391, procure a função:

public function setDefaultOrder($field){
 if (isset($this->_availableOrder[$field])) {
  $this->_orderField = $field;
 }
 return $this;
}

 
5 – Altere para esse código:

public function setDefaultOrder($field) {
 if (isset($this->_availableOrder[$field])) {
  $this->_availableOrder = array(
   'recente' => $this->__('Mais Recente'),
   'name' => $this->__('Name'),
   'price' => $this->__('Price'),
  );
  $this->_orderField = $field;
 }
 return $this;
}