Eh, ti sei risposto da solo..... "con il vecchio provider non c'erano problemi".
Hai controllato che le caratteristiche dell'hosting erano le stesse o superiori, prima di migrare il sito ?
Oppure è stata mal fatta la migrazione, o magari un errore del file .htacces, prova a disabilitare tutte le funziini SEO di Joomla, rinominare il file htacess in .old, svuotare la cache di joomla e del browser, poi riprovi.