How to fix "The requested Payment Method is not available."

There are several things that can be causing this issue. Basically what the error is saying is that the cart is trying to use a payment method (probably through the UI), but that payment method is not available for some reason. This may be because the payment method is disabled but has not been removed from the UI, or because of many other things.

Potential Reason #1: Are you using Store Credit to Pay for your full order?

If you're using store credit to pay for a order completely then you must have the Zero Total Checkout payment method option enabled in your Magento configuration. Many people disable this setting because they think it will allow their customers to checkout things in the store for $0, however this is not the case. The Zero Total Checkout payment method simply allows Magento to let the customer checkout without entering payment information in the event that payment information is not necessary. When using store credit to pay for the order completely, then no payment info is required and hence the need to have the zero total checkout payment method enabled.

To enable the zero total checkout payment option simply log into your Magento admin and go to System -> Configuration -> Payment Methods and look for the payment method titled "Zero Total Checkout". Now look for the enabled select box and mark it as enabled. Clear cache and voila, the error "requested payment method is not available" should go away and you should be able to checkout naturally.

Potential Reason #2: Is your UI out of date?

If you're using a fully customized checkout and your frontend engineer developer hard-coded the payment method options then you may see this same error message. The reason you see it is because the payment method is not supposed to be available to the customer/cart combination for whatever reason, however the UI is asking the cart to use it.

To solve this issue you can first go to the System -> Configuration -> Payment Methods section and ensure that the payment method that you're trying to use is actually enabled. If there are restrictions on who can use this payment method (such as country) ensure that your frontend customer is not limited by those filters.