Quite a bit of people find the default vimtutor too static for their learning style. Here's a list of sites that let you learn Vim in a more interactive way.
OpenVim Interactive Tutorial
I believe that this is indeed an interactive tutorial as it should be. The site runs a quite complete vim simulation in your browser, and guides you while you edit and navigate text. The good thing of the web app is that you can start learning shortcuts even before you install Vim! Plus, it gets bonus points for being open source and showing their test suite online.
VimGolf
VimGolf is a list of challenges for modifying text with the shortest keystroke sequence. While not directly an interactive tutorial that guides you hand in hand, it lets you think and research ways to edit a block of text. You get to see some of the solutions that are better than yours, which lets you improve your style. You also learn to appreciate life-changing techniques, such as that typing ZZ is two keystrokes shorter than :wq
Vim Adventures
I admit that I'm a big fan of learning new skills through games. I strongly believe that mixing fun with education leave you with a more memorable experience, and this helps you retain the material longer. Vim adventures is a well-crafted game that lets you move throughout the world by using the vim keystrokes, defying obstacles with various shortcuts. After playing the first level (which covers basic navigation), you get access to the rest of the levels (2-12 plus one planned final level) for the next 6 months for $25. I am curious whether mastering the game controls improves your Vim navigation skills -- if you are observing such a correlation, please share it in the comments.
Shortcut foo
Another freemium app; the basic mechanic is that it asks you to type in shortcuts that do a described action. A quite useful feature is that it gauges your accuracy, so that you can determine where you need most training. The free tier includes beginner text editing and navigation, a total of 42 shortcuts. To unlock all Vim training, you need to pay a one-time fee of $5. Like in Vim Adventures, you are learning the shortcuts outside of the editor, so your performance within the app might be different than the one in the editor.
In conclusion
I hope that these tools improve your learning experience. Keep in mind that the best way to learn is to go through some of the pain and start using Vim on a daily basis.
Happy vimming!