Fatal error: Call to a member function rewrite() on a non-object after upgrade

I had the same issue, and beside clearing the cache, I had to set folder permissions on /var and subdirectories to 777 (don't worry, the .htaccess file in /var prevents everything to be "human" readable).

Looking at line 165

#File: app/code/core/Mage/Core/Controller/Varien/Front.php
$this->_getRequestRewriteController()->rewrite();

The method _getRequestRewriteController should return an object. For some reason, it's not returning an object in your system.

Taking a look at that method definition, we see the following

protected function _getRequestRewriteController()
{
    $className = (string)Mage::getConfig()->getNode('global/request_rewrite/model');

    return Mage::getSingleton('core/factory')->getModel($className, array(
        'routers' => $this->getRouters(),
    ));
}

Mage looks at the global/request_rewrite/model configuration node to find a class alias. In a store system this should be

core/url_rewrite_request

Which Magento then uses to instantiate a model. My two guesses are

1. There's a module with a different, invalid class name here, which prevents Magento from instantiating the object.

2. Your system is missing the Mage_Core_Model_Url_Rewrite_Request class file (at app/code/core/Mage/Core/Model/Url/Rewrite/Request.php), which is new in Magento 1.8

If you have a cache server like memcached try to restart it as well. I had the same issue and I resolved this way.