I am running J 1.5.8 in Legacy mode (cuz required for FlashOn Random Module) with JoomSEF 3.3.1.

I previously had sh404, but I uninstalled it and also deleted jos_redirection and jos_meta sh404 databases.

I am not sure what I am doing wrong, but after reinstalling JoomSEF, and enabling it, I get 404 errors for EVERY page except home. This is obviously only when I have Joomla SEF URL rewrite ON in Global config. I tried with Apache rewrite on and off in global config. Can someone tell me what I am missing? The documentation about the htaccess file was confusing, and I have done nothing with it since uninstalling sh404. I really want to make this work, as I didn't like sh404.