Activated but still "The requested Payment Method is not available." as registered user only

Try the following (ordered by the effort it would take, if one step does not help you, take the next one)

1. Check the allowed countries that you can configure for each payment method in the admin backend.
2. Check the error logs (system.log, exception.log after enabling them)
3. Debug into the \Mage_Payment_Model_Method_Abstract::isAvailable() method to see what is going on.

There are two places, where this exception is thrown:

/app/code/core/Mage/Payment/Model/Info.php:83

and

/app/code/core/Mage/Sales/Model/Quote/Payment.php:151

I would say the exception comes from the second part. If I understand it correctly, the first part is a real error, the second is a failed test.

as @Alex said, check \Mage_Payment_Model_Method_Abstract::isAvailable(), there is another "problem" which may be happen: Recurring profiles. Do you try to buy a subscription? Then maybe the method can not be used for this.

Do you have xdebug? It is a great tool for such problems, just hook into the isAvailable() methods and check where the return value is set to false.