When we upgraded our joomla site to 1.5, we ran into multiple issues:

1. Our template was not supported in version 1.5
2. A few components were not available in 1.5 (as they have never been upgraded)

Another big challenge that we faced was 404's, why? ... SEO

The content has been migrated more or less manually, as the automated processed didn't get the job 100% done. So, our article titles changed and as they were all SEO'd so the URLs changed.
Our website started throwing 404s left right and center, but there was nothing that was helping us, lot of tutorials which said about how to use error.php had all incorrect information, so after trying the easy fixes (reading and implementing) we had to go the hard way (thinking).

This is what solved our problem 100%:

The “system” template is included in the Joomla 1.5 installation. The file error.php located in <JOOMLA_ROOT>/templates/system handles display of error pages. In the beginning of this file (error.php), you should add the following code:

So, open it in editor and after line

defined( ‘_JEXEC’ ) or die( ‘Restricted access’ );
add code:
if (($this->error->code) == ‘404′) {
 echo file_get_contents(‘http://www.yourwebsite.com/your_custom_404_page’);
}

Please note: A lot of tutorials say that you should redirect to the error file, but for some reason that was not working for us. However, reading the content of the file did solved our problem.