What to Do?
As is true with so many other recovery programs, the first step is to admit you have a problem. No more dancing around or outright denial: If most of your testing is still manual, confess it. That doesn't mean you have to fall on your sword; management must be made to understand that the promise of automation was built on a faulty premise about what it would take, but not what it would return. Believe it or not, there are still many who haven't heard the news—announced on this very site and elsewhere—that capture/playback doesn't work and never did. The key here is to convince management that you learned your lessons from the first attempt and won't repeat them.
Next, you have to propose a practical, provable, and attractive alternative—practical in that you should pick a project and make it successful before planning an enterprise rollout, and provable in the sense of being carefully measured to confirm that success. Attractive is all about the business case; done right, automation can and does yield amazing returns. But don't sugarcoat the costs. Be up front about what it will take in terms of time, people, and money, in addition to the licensing fees for new technologies. Automation is worth it, but you have to make the investment.
Finally, you have to execute. This means not only conducting a thorough evaluation or proof of concept but also maintaining a healthy skepticism throughout the process. Actively question promises that seem too good to be true. Don't settle for the one or two references the vendor gives you. Ask around, and insist on talking to those who have weathered changes in versions, personnel, and technology to uncover the hidden costs of maintenance and skills required to keep the automation running.
You may wonder if it is even worth it to try again, and the answer is that ultimately you don't have a choice. If you don't make automation work, someone else will, because all those billions are an indisputable testament to the fact that management does, in fact, value automation. They may have been fooled about how to go about it, but not about the fact that they need it—now more than ever.