There are two places, where this exception is thrown:
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.