Please select a payment method for your order

**Please select a payment method for your order **
I have been able to turn this issue on and off in a property set up store with 1.3.9.c
If I have two payment modules installed, moneyorder and paypal express. The checkout via the paypal express button will not alow a checkout. Somehow the $_SESSION['payment'] value is being changed to moneyorder. This was found by showing $_SESSION['payment'] thought the checkout. Removing the moneyorder module resolved not being able to checkout with paypal. Turning it back on forced the red display "Please select a payment method for your order". Will provide data upon request.

I'm not sure what you mean by "property set up store", unless that's a typo from "properly". Even then I'm uncertain what exactly you mean by that.

Also, out-of-the-box, Zen Cart has the Money Order module enabled by default, and when I then enable Express Checkout (with nothing on the site other than demo products installed and the EC module enabled and configured), I'm able to checkout fine using either module either directly from the shopping cart or from the checkout_payment page. This is the same when I also remove the pre-installed COD and freecharger payment modules such that the only modules left installed are EC and MoneyOrder.
This leads me to believe that the problems you're mentioning are related to some broken HTML on the page (from a custom template perhaps?), causing the form fields/buttons not to work as expected, or from a custom addon that's intercepting the original checkout pages/flow/code.