I'm having the same problem. I've run a number of scenarios to test the various payment routes and I think I've been able to localise the issue in a a particular payment flow, which leads me to suspect there is a bug.

I've been able to replicate it a number of times using the Paypal Sandbox to test. This is a fresh install of Zen Cart as well with no modules or additions made yet. It appears to be occurring when you have Paypal Express setup as follows:

1. The only payment solution on the shop, the others are disabled.
2. Express Checkout settings are set so that a user still needs to see the Payment Page. So this might be by setting "Select Cheapest Shipping Automatically" to No or Skip Payment Page to "No"

The process seems to be:
1. Add a product to the shopping basket
2. Select the Paypal Express Checkout button
3. Log into Paypal and then click continue
4. Return to the shop. If you need to do shipping then you add this as normal and click continue. You then end up on the Payment Page.
5. On the payment click continue and this is where the "Please select a payment method for your order." error appears.

I have noticed however that if I click on the shopping basket and select the standard checkout process then on the payment page the Paypal Payment icon and information appears. However, if I tried using the Paypal Express button again on the Payment Page I do get an error.

The other thing I've noticed is that if I add another Payment Option, eg Check/Money Order then if I do the Paypal Express Checkout route then it does appear to go through.