Magento 1.5 Cart – How to Sort Cart Items

I am trying to sort the items based on the order they were added to the cart (oldest at the top, each item added under that). Is there any logical method to the way cart items are sorted in Magento 1.5? I can't seem to find a pattern!

I've been trying to sort using this on /app/design/frontend/default/mytheme/template/checkout/cart.phtml

$cartitems = Mage::getModel('sales/quote_item')->getCollection()->setQuote($this->getQuote())->addFieldToSelect('updated_at')->addOrder('updated_at', 'asc');

$items = array();
foreach ($cartitems as $item) {
    if (!$item->isDeleted() && !$item->getParentItemId()) {
        $items[] = $item;
    }
}

And then looping though the items per usual…

<?php foreach($items as $_item): ?>
    <?php echo $this->getItemHtml($_item) ?>
<?php endforeach ?>

I also need to sort cart items on a mini cart that drops down when you hover over a cart link in the header. It's working great except the ordering.

$items = Mage::getSingleton('checkout/session')->getQuote()->getAllItems();

I've tried a bunch of different ways to sort, and just when I think I have it, all I need to do is change the qty of one of the items and they are all out of order again.

Can someone please point me in the right direction? I have found a couple things to try but nothing seems to be working.