Part of the issue may be in the way Scrum becomes part of the organization. If the organization believes that it will provide real value then, then real change can be affected. If the organization feels it is an IT problem or it is something you are trying to get pushed into the organization without real buy-in you'll find it will be viewed as "Michael's Process".
Your problem in my opinion is the most common and hardest to overcome. How can Scrum be introduced in a transformative way? Who should be the PO and who should be the SM? How do we find a knowledgable PO that is capable enough to understand the process, yet has authority to be the final say to stakeholders?
Those answers in my opinion are not addressed by any Agile process, but are by far the most important.
I believe the answer lies in the psychology of people. How can we transform a culture to affect real change, and not just mask the same old process under a new name? They have to believe in the change and accept the empirical (and transparent) nature of the process. They have to want to change the way they have been used to doing things.
Many times this is hard to accept from someone who is familiar. Bringing in a coach can help with that many times. It may be viewed with more respect and open mind. But, every company is different and will vary because of many factors.
But, let me say this. Not everything needs to change. You don't have to do user stories. If they are comfortable drawing bulleted lists on white boards, snap a picture of it and use that. Later, after some wins in the process come back and revisit changing that. You don't have to educate the stakeholders on using any new process. You need one (or hire a new one) to step into the PO role. You could divide parts of the job. You could have a stake holder responsible for approving the backlog and prioritizing items, while you do the more technical aspects of keeping it groomed and setting meetings. Conversely, you could give some of the Scrummaster's role to another team member. Indeed, finding the super PO will be very hard.