Your particular problem is well-known and has been documented in a few places including the Magento Wiki:
add this to your .htaccess file
RewriteEngine On
RewriteCond %{DOCUMENT_ROOT}%{REQUEST_URI} !-f
RewriteRule ^.+.php$ /bogusfile
Then try to reload your setup page.
If you do not have Magento setup in the root of your server, make sure
to add the following to your .htaccess file.
RewriteBase /yourbasepath/
Once that is verified, there are a couple things you can do to fix
this, but we’ll start with the one that usually works.
In your web root directory, there should be a file called php.ini.
Rename this to php5.ini.
If there is no php5.ini file. Create the file and upload it to your
root directory.
If that doesn’t work, add the following to the end of your newly
renamed php5.ini file:
cgi.fix_pathinfo = 1
And if you’re still getting the error, add the following to the top of
your .htaccess file:
Options -MultiViews
The first one usually does the trick. If you don’t see this file in
there, then create a blank php5.ini file add add the line listed on
the second suggestion.
If all of the above has not worked, KEEP your changes, wait exactly 24
hours. Go back to youraddress.tld/downloader and try again. You may
just be cached and for some reason it takes a bit longer then I was
used to. Keep your chin up!
If nothing above worked, call GoDaddy up and have them either rename
this for you, or make sure you’re on PHP 5.
Best Answer
Starting from Magento 1.5+ you need to install using the Magento Connect 2.0 key, as you correctly figured out.
In addition, the core package from Magento is listed as beta. You will need to update your stability settings to allow Magento to install 'beta' packages: