wp-login.php 404 on clean sub-directory install

Having a problem with a brand-new clean install.

http://blog-stage.mydomain.com/wp-login.php
loads but cannot load the stylesheets

http://blog-stage.mydomain.com/index.php/wp-admin/css/login.css?ver=20090514

When I enter my credentials, I am re-directed to
http://blog-stage.mydomain.com/index.php/wp-login.php
which loads a wordpress 404 page.

I've done this before successfully on other hosting solutions, but am banging my head against the wall for the client. I'm sure it has to do with rewriterules or something, but assistance would be greatly appreciated.

Thanks