Show us the redesign vs original design. The best way to tell if a design is "better" than the original is to put both version in front of brand new users who haven't developed usability habits yet.

Sometimes when you make an app the first time, it's badly designed but people get used to the bad design. Then when you improve it they have to relearn everything and that's why they're pissed off.

Another thing you can do is "incremental design". Change things little by little over time.