You can use PayPal or Credit Card via PayPal Express

Also, I tried with just PayPal Standard and FREE SHIPPING! freeshipper and I still cannot reproduce the error ...

Are you able to use something like Beyond Compare from scootersoftware.com to see if you have any bad files on the Server?

If, as a test, you install the Check/Money Order a and try checkout if you select Check/Money Order and enter your 100% Discount Coupon, does it work?