It's a great question and I applaud you for accepting the challenge of such a big upgrade leap. I'm not entirely sure there's a clear answer to your question. Some companies are great with a more tops-down driven strategy so you could probably ask a smaller number of people, focusing on your management tiers and run with what they tell you. On the other hand, you are a widely diverse base of users so of course you'll want to give people the opportunity to chime in. I think you'll know you've hit enough when you schedule a focus group and no on attends. Or you reach enough people that say "hey, whatever you implement is fine."
Keep in mind too that people don't always know what they need. Something about asking people in the early 1900's what they wanted in transportation and the ideas were all for better horse carriages, when in fact what was needed was an automobile. Know what I mean? Sure, talk to the people, get a good solid sample. Yet at some point you have to take a leap and embrace the new features and drag people along with you. Do it with enthusiasm and joy!
And let me know how it goes and what you decide. We're here cheering for you!