Post subject: SEO settings result in 404 error

Hi,

Joomla (1.5.6) has been working fine with all 3 SEO settings ON in my website. The server had the PHP running as an Apache mod. After I got my server changed to be able to use FastCGI, though perhaps not related to FastCGI, I get 404 error with some pages, and SEF URLs are not displayed. I have been unsuccessfully trying different SEO Settings and changing .htaccess so far, following instructions from this forum.

This is what I found:
Regardless of the SEO setting, articles which are 'uncategorised' eg. pages like about.html always work. When 'Search Engine Friendly URLs' & 'Use Apache mod_rewrite' are ON the SEF URLs are displayed correctly, eg.
http://www.mysite.com.au/about.html
And, when these settings are OFF, the same URL is diplayed, as expected:
http://www.mysite.com.au/index.php?opti ... &Itemid=65

However, articles that have been assigned to various Sections and Categories do not display the SEF urls regardless of these settings. They are always like: http://www.mysite.com.au/noideas&catid= ... &Itemid=70. And, with these 2 SEO settings ON, these pages return with 404 error. I have also tried with a clean install of Joomla and the sample pages like "Welcome to Joomla" always have 404 error.

When these two settings are OFF, these pages reroute/forward to the frontpage again (browser displays the URL, eg: http://www.mysite.com.au/index.php?opti ... &Itemid=65) and no 404 error. The actual page is not displayed.

htaccess.txt has been renamed to .htaccess, and is located in the root. Joomla is installed in the root. Rewriterule (.*) http://www.google.com takes you to Google.
Here is the htaccess file and info from JST-post. See the error messages displayed (in red) in the 404 page. Thank you in advance for your help.
-------

Code:

##
# @version $Id: htaccess.txt 10492 2008-07-02 06:38:28Z ircmaxell $
# @package Joomla
# @copyright Copyright (C) 2005 - 2008 Open Source Matters. All rights reserved.
# @license http://www.gnu.org/copyleft/gpl.html GNU/GPL
# Joomla! is Free Software
##

## Can be commented out if causes errors, see notes above.
#Options +FollowSymLinks

#
# mod_rewrite in use

RewriteEngine On


########## Begin - Rewrite rules to block out some common exploits
## If you experience problems on your site block out the operations listed below
## This attempts to block the most common type of exploit `attempts` to Joomla!
#
# Block out any script trying to set a mosConfig value through the URL
RewriteCond %{QUERY_STRING} mosConfig_[a-zA-Z_]{1,21}(=|\%3D) [OR]
# Block out any script trying to base64_encode crap to send via URL
RewriteCond %{QUERY_STRING} base64_encode.*\(.*\) [OR]
# Block out any script that includes a