Your teaching strategy should take into account not only the complexity of the game but also the amount of innovation. Focus first on the experimental parts of the game, knowing that the more familiar mechanics have already been successfully taught before (and therefore a solid reference for teaching them can probably be found and adapted).
Following that, look out for parts of your game that may not get in the way of immediate progress, yet run the risk of having a long-term effect. For example, players may not realize the importance of particular resources and throw them away, only to realize 30 hours later that by doing so they're now lacking the necessary materials to upgrade their equipment. ...
