Problem with Joomla built-in SEF

Hello everyone,,
I'm looking to set up SEF URLs on a Joomla site. I downloaded the SEF Advance trial version to check the component would work on the site, but have not installed it yet, because the documentation says that Joomla's built-in SEF must be working. However when I turn on Joomla's built-in SEF, some of the site doesn't work - some links are dead, or give me 404 "Article not found" errors. Turning on Apache mod_rewrite makes even more pages crash, and I get "Not Found" and "404 Not Found" errors.

I get the same with sh404SEF: most of the site works fine, but some links (the articles in the Blog section, for some reason) don't work or give me "404 - Article #0 not found." Whether with or without .htaccess selected in sh404SEF config > Advanced > Rewriting mode, makes no difference.

I have checked the following:

1. I have an Apache server
2. mod_rewrite is enabled
3. My server allows .htaccess override (I've tried replacing my .htaccess text with "Redirect /google.html www.google.com " and it does indeed redirect me to Google)
4. SEF URLs are turned on in Joomla Config (giving me, I believe, the line "JConfig { var $sef = '1';" in configuration.php)
5. My htaccess file is called .htaccess (with dot) not htaccess.txt

From other posts on the forum, I think Mr Sakic's first response would probably be that either the .htaccess or mod_rewrite is faulty. But I asked my webhost who says there is no problem with the server setup. (They might of course be wrong?)

It's a bit of a puzzle, but I'd like to install this component so I'd appreciate suggestions. I've looked at the forums etc but don't see anything quite like this, apologies if I missed something.

I am running Joomla 1.5.2, Apache version 2.2.11 (Unix), PHP version 5.2.6, on a Linux server.

Hello,

What do you mean by "SEF Advance trial version" and where did you download that?

Thanks.