Should you concede to user demands that seem clearly inferior?

Currently working on a ground-up (not just the UI) reimplementation of a whole, existing system. Because it's internal we've been able to work with its existing users during the process, and get their feedback on what they want doing.

One of their existing UI elements involves nested data. Currently, they have to take the following steps:

• Type text into a textbox to narrow the selection in a drop down.
• Chose one of the results from the drop-down box, which populates a treeview.
• Browse and expand the treeview, and select a branch.

The list in the drop down is not long enough to justify the text filtering (about 75 items). However, under each of these items there can be a very large number of items and sub-items in the treeview.

We replaced this with a single treeview which has the 75 items at the top level, each one expanding down. This seems very easy to use, to us: as each level expands you can, if necessary, just scroll down the list with the mouse wheel and find what you need.

But the users hated it. They wanted to go back to the old way. When we watched them using the new system it seemed quite clear that the biggest problem is simply that they weren't used to using scroll wheels, so the left-right swipes required as each level was expended and then the scroll bar grabbed and dragged were slowing them down.

We pointed out how useful the scroll wheel was, but they're not used to scrolling, and don't want to start.

To my mind, the way we redeveloped it is unambiguously better. But the user base was equally emphatic in rejecting it. So today, to the complaints of my fellow team members, I removed our new implementation and set it to work in the manner the users were used to.

What was the right course of action here? Is there a point at which the user's fear of change becomes an important UX consideration in its own right?