Ask your web host to look at the web.config file created by the piwik installer. it’s possible this is incompatible with their system configuration. You could try removing it – with the caveat that you’ll be removing a layer of security.
There doesn’t seem to be a Piwik created web.config. There is one in the root of the website, but that came from me. I deleted the Piwik directory and reloaded everything in case I forgot to do a Binary upload. When I restarted the Piwik setup I noticed the PHP version it found was 5.1.3RC and not the one the host tech support told me. I have asked them to upgrade to the current version, so I am hoping that works, because so far, nothing has changed.
I don’t expect any answer until Tuesday because of the Memorial Day holiday.