I have similar problem. I have reinstalled wp twice and mysql base too… Everything stops at that ‘404 not found’ error.
Is it possible that “PHP safe mode off” is required to install wordpress on the server? My web hosting provider says that many of the users say that they have problems with addons as they require safe mode off?