Common problems when enabling Search Engine Friendly (SEF) URLs
From Joomla! Documentation
Usually this has something to do with your host's settings. One solution that commonly works is to enter a value for the $live_site variable in the configuration.php file found in the root directory of your Joomla site files. The value of the variable must be manually edited.
Typically, it would look like:
var $live_site = 'http://example.com';
But, if you access your Web site in a folder, it would be like this:
var $live_site = 'http://example.com/joomla';
- See Joomla! v 1.5 SEF URLs Scribd by Benjamin Hättasch which contains step-by-step instructions for installing and trouble-shooting your SEF URLs.