Strange SEF URL error in Joomla

[abrodski]

I transferred my Joomla site to hosting and the site was all messed up and I got 404 errors etc.
I was advised by someone smart to change my SEF URLs back to NO and now the site works...
Why is that and is there a way to turn ON SEF URLs and keep the site in working condition?

P.S. This SEF URL feature is NOT crucial to me, but still...its very desirable.

[willybfriendly]

Which version of Joomla?

[abrodski]

1.5.11
I kinda found a solution...I renamed htaccess.txt file into .htaccess and turned on both SEF URLs and Apache mod_rewrite.
It solved the problem.
Though I read somewhere that I had to just make a file name change...
So what's the story behind all of it and should I keep Apache mod_rewrite ON?