404 message after following Craft installation instructions
How did you create the database? 
Did you use phpMyAdmin or did you create it manually, or using other tools?

I've had a similar 404 error last week (db was created with phpMyAdmin) then I created database with Sequel Pro and that resolve the problem.