Two main things I've seen and done that has worked: 1. Deliver fast enough that people don't care as much about estimated lead time beyond "it's fast enough"; 2. Show that more complicated estimation schemes are not producing anything significantly different than the simpler counting stories.