I did a small offering to my co-workers on regular expressions. The approach I decided to take:
Emphasize the gentle learning curve of regular expressions. (Whut.) In other words, if you know them a little, you can use them a little. Let the anchors be their anchor: ^ and $, then build from there. The next logical steps are: .+ and .* homegrown character classes built-in character classes (\w and the like)
I moved quickly to using backreferences to replace strings, since we often have to generate scripts from lists that the users send us.
Try to find things they are actually doing and show how regexps can replace "elaborate string manipulation using only built-in string functions." Remind them that less code means fewer bugs. Enlist the help of someone who works on another team and see what they do that can be made easier with regular expressions. (If that team is a large team, so much the better.) If your audience sees that you've taken the trouble to tailor your presentation to their everyday needs, they will respond.
I'd also keep it short. The goal won't be to teach them the ins and outs of regexps, just to let them see how they can be of value