Are you installing WordPress manually or you use Fantastico or any other autoinstall ? If you use an autoinstall script provided by your hosting provider i would consider contacting them. Otherways, if you manually upload the files on the server check that you are doing it in the proper way, and if you are sure you are doing it the proper way, the only suggestion i can give you is to contact your web hosting company and ask them to look into it.

I have no problems with WP on my server.