I just finished teaching SANS' two day class on building a high-impact security awareness program, where we had a fascinating discussion on gaining stakeholder support. A trend many of us are seeing is that the greatest support for security awareness programs does not come from security, but often from other departments totally un-related to security. It seems that many information security teams are so focused on technology that they often believe the HumanOS cannot be secured, if they even think about it at all. In addition they often do not understand the human problem as they have never been trained on it. On the other hand I'm finding that other departments (think accounts-payable, human resources, or operations) are huge supporters of awareness programs as they see every day just how desperately their staff need the training.
I'm beginning to think that when looking for stakeholder support, don't start with your security team but start with the people who will benefit from the training the most. Talk to your other department heads, see who is interested and find out why they want your training. Then use that to build your stakeholder support.