Can't get to any payment options in checkout - not even a check payment.

[dixie]

I am on a shared SSL host server. Since my install several days ago, I have never been able to get any further than to the payment part of checkout. When I click on Pay With Check, I get the following:
The server encountered an internal error or misconfiguration and was unable to complete your request.
Additionally, a 404 Not Found error was encountered while trying to use an Error Document to handle the request.
My host does not know what the problem is. I have the check module installed and configured (as much as I know how).
I am using the latest Prestashop.

Is it true that Prestashop will not work in a shared hosting environment - read this in the forum.

Can anyone steer me to the direction I need to go to fix this?