We don't have them out here (although we just got a memo about it so maybe they are starting up) but I flew a bunch of them before leaving the east coast last year. They work ok IF they are programed correctly and IF your aircraft has good VNAV and auto throttles. In the CRJ without either of those things they are an incident waiting to happen. The benefit I did see for them was reduced radio clutter. In the past when descending into someplace like DCA you'd get about 5 different altitude assignments on the way down. With a descend via clearance, there was only one. Multiply that times X airplanes per hour and it results in a lot less talking. The fuel burn issue is also true IF the procedure was designed for you. A RJ doesn't do a throttle idle decent that same way an Airbus or 757 does. A way of fixing that problem is giving windows on the arrival so most fixes "CROSS XXXXX BETWEEN FLXXX and FLXXX".
Also, a controller telling you what transition a fix is on if getting cleared somewhere farther down the line on a different transition is VERY helpful. Most FMS boxes load an arrival by "Arrival Name" and then "Transition". If you are cleared direct a fix three in from the initial transition fix the only way to do that is to load the transition (which is unknown if the controller doesn't tell you or until you find the fix they want you to go to on the chart and then backtrack up the arrival until you get to the transition).
Finally... You think descend via is bad... wait until we start the climb via clearances.