I second Joel's trust and value. Especially the former. As long as people in the organization don't trust you it's likely it will fail.
However I'd take a step further. You may or may not have trust relationship with people around. So you might want to actually show them the value of change.
What you need is small group of people who you can convince to your idea. Then you need to figure out how to run it in small scale. Most of ideas don't have to be implemented company-wide from the day 1.
If we took as an example implementing new approach to project management it's enough to find a single, possibly small, project with people willing to try something new. Actually if you want to run something in small scale you probably won't even need to bother decision-makers, and if so, they would likely agree as small experiment doesn't really hurt them.
Then you need consistency. I've seen a number of good ideas which were abandoned only because people expected instant results. Well, most likely they are not coming. So you better get your people prepared for a marathon, or at least middle-distance run than a sprint.
After some time, when results of small-scale change are visible it's time to spread the word. Actually a bit of boast isn't probably that bad idea. Anyway, when people see that it works they're more willing to jump on the bandwagon. And then it's easier to convince authorities to implement change in big scale.
And that is when you can make great use of veterans from the initial team, as they know how the thing works and can serve with their knowledge when spread over different teams within organization.
This is how you earn trust and show value.