Fortune Teller is, to be clear, one of the weakest attacks in the game. Early on, especially with any trashing, it can provide a Chancellor effect to your opponent, cycling through his deck and dumping it in the discard if it doesn't find any Victory cards, and thus helping him get to his new, more powerful cards quickly. And unlike other weak attacks (Bureaucrat, Cutpurse, Torturer to some degree), it improves not at all from playing multiple ones per turn, as the net effect to your opponent is the same.
If Native Village is on the board, Fortune Teller becomes even weaker. Each time you draw Native Village, if your opponent plays Fortune Teller, you can safely squirrel away a Victory card to your mat. Like the
Apothecary/Native Village combo, when you begin greening, each play of Fortune Teller is another opportunity for you to clean out some green from your deck and keep it moving along; this is especially true in multiplayer games, where more than one person might have purchased a Fortune Teller. Also, if you're fairly certain a Fortune Teller will be played, you can be more aggressive about buying green, since you know you'll be able to clear it out of your deck.
Granted, Fortune Teller's attack is so weak that you might just ignore it. But if your strategy would be happy to incorporate a Native Village or three, it's a great way to turn Fortune Tellers from a nuisance into a key part of your deck construction.
Also might work to counter other cards that influence the top of your deck: Ghost Ship, Spy, Sea Hag, Scrying Pool. (I haven't tested this, so will need to verify/get other people's thoughts.)