Update: my problem is solved and it was a service provider issue. A tip: when your provider says they support all the WordPress requirements, ask them if they support them on the server your stuff is on.
I need to jump into on this, because I’m having a very similar problem. I uploaded the WP folder, renamed as “blog”, to my host server. Going to http://www.websitename.ca/blog/wp-admin/install.php brings up this message “t doesn’t look like you’ve installed WP yet. Try running install.php.” When I click the link, I get this URL: http://www.websitename.ca/blog/wp-admin/wp-admin/install.php. I tried the load the photo to the wp-admin folder thing and I can access the just fine.
(The host I use lists its versions of mySQL as 3.23.58 and of PHP of 4.3.1, which meets the requirements for WordPress.)
I’ve tried reloading the WP folder to the server and get the same problem.