I've done a few installs of Craft and never had a problem. I'm currently trying to do an install on a new server under a subdmomain and getting the following results…
This results in 404 http://staging.example.com/admin
Using /index.php/admin or /index.php?p=admin results in Internal Server Error 500.