This is the however
If the majority of users have rejected a design, it seems ludicrous for any UX professional to insist on that design because 'they know better what's good for the users'. Quite appropriately, the majority of the replies to your question follow that thinking.
I would, however, like to offer an alternative take on this, which goes well deep into the very essence of what we do.
Rejecting change is a survival skill (the status quo bias)
You can argue that the fundamental principle behind any human behaviour, and the root rationale behind nearly all man-made things, is the wish to find order in chaos.
To do so, we must identify patterns. Life could not have existed without such ability - a baby exposed to a different language every day would learn any language. If your girlfriend's face and general appearance would change every day, you would find it rather impossible to keep her as your girlfriend - after all, you wouldn't be able to recognise her most of the time (and while having sex with a stranger might sound fun, most people eventually opt for the stability, or order, relationships offer).
The problem with changes is that they break patterns, which must trigger some cognitive 'discomfort'. Once's you have learnt something, you don't want it to be taken away and forced to learn something again.
This is a key challenge in UX - although changes are often for the better, experienced users often dislike them (even if the benefit is clear sometimes).
So rejecting changes is a survival skill (if you want) and a completely natural one.
It happens that the older we get, the more firm our understandings become and thus the more we reject change. This partly explains why young people are much more welcoming new technologies than older ones.
The Apple PCIe story
Somewhere around 2007 (if I'm not mistaken) Apple came to give a talk at then my school, which specialises in audio and film production. They could not have picked a worse time - 3 month earlier, Apple have announced the discontinuation of PCI based Macs in favour of the (then unheard of) PCIe interface.
For the school this meant an estimated 5 digit cost over 2 years, and ditto for pretty much the whole of the professional audio and film industry (which were relaying on a particular, highly popular PCI DSP hardware).
Needless the say, a lot of grief, disappointment, and even anger were thrown at the Apple representatives during this talk. But their answer was a winning one. It went along these lines:
At Apple, our aim is to craft the future of technology and provide our customers with cutting edge hardware and software. If Apple were to focus on dated, under-performing technologies, it would never have existed today.
Rejecting change is rejecting progress
There is much more to the embracement of change than what may first meets the eyes.
Mankind would have never achieved what it has without change - No change, no progress.
Novel innovations, by virtue, explore unfamiliar territories. Many scientific breakthroughs were the result of popular patterns being challenged.
To give just two lame examples, both when stereo sound and colour television (the ancestor of the screen you are looking at right now) were invented, people were seriously doubting the usefulness and value of these innovations - in the case of stereo, it took 24 years before the invention became a commercial product.
My point is that while totally understood from a user point of view, one should also understand the consequences of allowing change aversion to prevail.
Be brave, triangulate
You should really question what side you are on, and what is your true role and purpose in this field.
If your users have disliked the change, you have one evidence against it. But if a triangulation with a other empirical research methods would prove otherwise, you have strong case to overrule the users.
I wouldn't rely on your own expert opinion, but perhaps use some predictive evaluation techniques, or user testing with those unfamiliar with the system.
Anyhow, I don't think the answer is as clear cut as otherwise seem by most other replies.