If you want the cheapest solution, you might want to try Noca (www.noca.com) which supports recurring transactions but everything happens through ACH and hence it has its own set of hassles.
We've also had quite a few problems getting our transactions to complete - about half of the transactions from this month are still pending.
Note: I haven't checked out spreedly yet, but I've heard similarly good things.
I wrote a quick Rails plugin to interface with the recurring payments with Braintree. It doesn't implement all or their API's, but it's enough to handle monthly recurring billing for Outspokes. I pushed it up to github in case anyone finds it useful. Let me know if anything's confusing about it. I'll polish it up when I have more free time.
Incredibly simple API with libraries for most languages. But it does require an Authorize.net merchant account to tie into.
Haven't tried it yet, but looks similar to spreedly.
also try cariboucms.com if you're looking for a full cms with member management subscription capabilities(great product)