I'm a developer for an app sold on the Mac App store, so I can assure you that supporting Versions is not that big of a deal. The biggest problem for me was making my app play nice inside the Browse Versions interface.
The real issue is testing the app under Lion AND back on Snow Leopard to make sure you dont break something on Snow Leopard. There is also an app upgrade review and approval cycle done by Apple for products sold on the App Store. My gut feel is that the review staff is being flooded right now with application updates for Lion by virtually all of the products on the App store.
I do remember that Snow Leopard broke things too when it went live. (But then Apple has done at least 8 updates to Snow Leopard after it was released.)
By the way, the old way of saving works just fine for apps that dont yet support Versions.
Versions does take a bit to get used to. It is a paradigm shift from the way apps are saved over the last several
decades.
Apps that require custome hardware and custom device drivers will most likely be the last to convert to Lion. Years ago I was a ProTools user and they took over 6 months after Tiger was released to release a compatible upgrade (and they charged a lot of money for it too).
The vast majority of apps dont fall into that category. They just have to do a ton of testing, which takes time.