The biggest win with Magento is they've solved a lot of common e-commerce programming problems really well. Payment gateway and shipping integration are top notch, and if you've ever struggled with a payment processor's poorly documented API or had to download a UPS "enhanced" PDF to get at their service information, you'll know that's worth the price alone. The company behind Magento did a ton of e-commerce consulting before building Magento, so they knew what kinds of things needed to be solved. These things are exposed pretty well from a customer point of view.
Magento has an incredibly robust module system for overriding, changing, and adding to core system behavior. Part of the negativity you see directed at Magento is people used to dealing with simple PHP scripts encountering a module system for the first time. Remember the first time you saw Drupal? (what's a hook? a node? Argh!) There's also a growing number of free and commercial extensions written for Magento the fill gaps people have in it's functionality.
The other big gripe is performance and cacheing. Magento pushes the edge of what you can do with OOP PHP code, and relies heavily of internal caching of objects and configuration to get acceptable performance out of the system. This caching that causes confusion for developers trying to learn the system. Also, you're not going to run this on a $5 Dreamhost account.
Magento uses some components of the Zend Framework, but it's a really a framework in and of itself. If you're familiar with MVC (CakePHP, CodeIgniter, etc.) patterns it's not that difficult to get up to speed on what they're doing. The template and skin systems are separate from the back-end module system, so the main gripe your designers will have is learning where the files they need to edit are, as well as learning the magical incantation to grab what they need.
Magento uses straight PHP for its templates, no smarty required.
End of the day? If you've got sharp people it's not that difficult to conceive of how it works, and it solves so many problems out of the tarball that it's worth the investment. Every system has it's crap to deal with. If you had a crap free system, you wouldn't be considering the switch. My biased, I do this for a living, advice is to bring in (perferably on-site) a Magento expert for your first project and let the team soak up as much knowledge as possible. A few weeks with someone explaining how it works it all you need.