When the sef is off what ur urls look like?are other components working all right?have u enable apache mod_rewrite,both in ur server and joomla?are u using latest ver of sh404sef?please disable mod_rewrite and rename htaccess and check if ur problem resolves.