I had same problem, after saving new "payment preferences" (carrier restrictions in my case). The payment stopped working for one carrier. Resetting payment module helped.
Edit: actually id didnt, I have two carriers and no matter what I do always for one the payment is unavailable (despite settings in "carriers restrictions" which I keep always selected). There is some bug with how the payment module decides if it can be used for specific carier.