I think the problem is in your hosting. Ask hosting's support about mod_rewrite.
Does it work well without sh404sef? What links does Joomla output? It looks like mod_rewrite doesn't work.
What about .htaccess? Did you rename htaccess.txt to .htaccess? Is SEF plugin enable? And SEF in Joomla settings?
Describe your problem. I don't know what to suggest.
I've just tried the latest versions of K2 and sh404sef. So, it works well. I suggest you to download K2 2.4.1 and sh404sef 2.1.6.
I think the latest K2 is fixed, but I may be wrong. Which versions of K2 and sh404sef do you use?
I've got a problem with K2 while using sh404sef component. Pagination doesn't work. It always shows me link to the first page on each link. Does anybody know how to fix it? Or how to remove "/component/k2/" from joomla sef? )
still using pagetitle...
it takes page title, but it should be aliases..
Thanks. I've reinstalled sh404sef with default settings, so it works perfect.
More