Error 404 on installation

Permalink
I have seen this answered in dribs and drabs all over the web, but would love to get the definitive answer.

I am installing Concrete and i have uploaded all the files (777 access etc) and then when i click 'Install concrete' i get an error 404 page.

Please help, i'm desperate! I've heard maybe it is Mod_Rewrite but what would i have to do to fix it? Any help greatly appreciated.