Something wrong with your SEF configuration. Are you using mod_rewrite? Is your .htaccess configured correctly? I recommend downloading latest Joomla 1.5.x install package and grabbing the htaccess.txt then uploading to your server and renaming to .htaccess to ensure your htaccess file isn't modified.
Please also ensure the $live_site is '' (blank) as instructed earlier in your configuration.php. This should not be changed.