I deal with this every day, and frankly perception is irrelevant. The way I tackle this with a customer is asking whether their perception of their money is what buys them things or their actual money?
The REALITY is cloud is NOT a cost saver, in many, many cases. It CAN be a cost saving mechanism, but if you think that your data doesn't have value enough to be protected, don't protect it. Just don't expect Amazon to give you your lost revenue back when you lose a customer because you didn't properly protect the data and didn't bother to understand what your "cost optimization" really bought you.
Cloud is not new. It is a new spin on the same outsourcing, SaaS and IaaS marketing schemes that have existed for decades. You still have a fiduciary responsibility to your shareholders and your customers to protect the data, regardless of where you store it -- whether that's in your datacenter or in someone else's, whether that someone else's is called a cloud, a block of cheese or an imaginary land of rainbows and unicorns. :-)
What licensing mechanism is needed other than the FETB model we have in use today? Whether the TB is in the land of rainbows and unicorns or on spinning disk in a physical datacenter you own, if you're backing it up with NBU, it needs to be licensed. Why should there be a different license modely because of where you choose to store it? I'm curious what you're thinking about here. Why should Veritas make less money because you decide that you aren't skilled enough or don't want to pay to run a datacenter of your own? Aren't we still providing Enterprise backup capabilities, regardless of where you decide to put the data? If you decided to move off Enterprise storage to USB drives, does that change what we do? This is an interesting argument I'm hearing more and more -- that because hardware ownership is being denigrated and commoditized, all the other elements of the infrastructure should follow suit and declare themselves value-less. I'm genuinely curious what you think should happen here.
Also, remember not to confuse putting something in AWS with being a backup solution. AWS isn't a backup solution unless you deploy backup into an AWS infrastructure. AWS is storage and compute. It's not ITaaS, it's IaaS, very different things.