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.