One mechanism (which has similarities to a mechanism described by Joel as being used at Fog Creek) is essentially an auction.
Start by getting everyone who should have a say together. This is likely to be one or two representatives from each of sales, development, support, marketing and so on.
Each of these representatives or teams is given a "budget" according to their say. The way the budget is divided up is unlikely to be even - Sales should probably have a far larger say as they represent the users, or the prospect of more money - but that's up to you. The only thing I'd suggest is that no-one team should have 50% or more of the budget.
Get all the possible changes in the next release on the table and describe them, their benefits and how long they'll take to develop so that everyone understands them. They should be broken down into similar size chunks as far as possible and no one chunk should take up 50% or more of the time available in the next release.
Now people get to spend their budget. Each team / individual divides their money up between the things they want to do. You can spend all of it on one thing or divide it between many.
Once that's done you work out what fits into the release, starting with the thing with the total most money against it, going down until you run out of time in the release.
You might then want to allow them to adjust their "bids" and repeat but generally you want no more than three rounds.
Why does this work?
Most importantly for me it taps into the knowledge people have about what's important and allows them to make choices based on that.
If the developers and / or support know that, say, refactoring the database is key to them, they can spend their whole budget on that (note: this is why no-one should have 50% or more of the budget and no single change should be more than 50% of the release - if you breach those then individual team's ability to say "this is really critical" falls away because they don't have the clout to make them happen even if they sacrifice everything else).
What you're not doing is forcing them to quantify the benefit in ways that don't really make sense to them, they just get to say "we know this is important and we back this up by saying to us it's more important than anything else and we'll sacrifice everything else (or a bunch of other things) to do it".
Similarly if sales absolutely must have that holographic interface they can do so but they will have to make sacrifices (in the form of having less money to bid for other things they believe will drive sales) to get it.