A questo punto ti consiglierei anche di vuotare la cache lato sito, lanciare anche da menu strumenti un controllo globale (non fa mai male) e magari di verificare anche presso il tuo fornitore di servizi hosting, se magari qualcosa nel frattempo è cambiato, se il mod_rewrite è abilitato, etc., se dici che non hai toccato nulla allora in ogni caso ti aggiorni il tuo joomla e poi comunque se la cosa non si risolve neanche così allora controlla come ti ho detto sopra il tuo hosting.
A proposito, usi altri componenti per la gestione seo? Se sì disinstallali, basta tranquillamente usare le opzioni native di joomla per gestire il seo.