Ask HN: What is the best way to train new users on software?

I'm a grad student who is currently building a software startup with a couple co-founders. While our end goal is to build software that helps people share files/relationships/emails in the enterprise, to start we wanted to see if we could make email search better.

We started with Gmail since it's a little easier to develop for than Outlook and we created a pretty cool Chrome plugin that basically allows you to have 3D search within Gmail and Google Apps email accounts. The problem is that it's not the most intuitive thing in the world. To start we put together a short video walking people through the process of using the tool but have found that very few people actually watch it. Would we be better off using a greyed or blacked out screen with white arrows pointing to various features the first time someone logs in ala Pulse News Reader? What are some other ways we can train users on the various features?

I really appreciate the feedback and advice!

Oh and our current plugin/video can be seen at http://bit.ly/V10fFK