Sounds like I haven't explained things very well in the tutorial. Do you have any suggestions for improving that? Anything in particular which put you off?
Well, take what I say with a grain of salt. I learn kinesthetically, and I'm somewhat of a purist when it comes to game explanations. I believe that gameplay design should be accessible enough for players to understand it intuitively within a few moments in the game. This is one of the cornerstones of Shigeru Miyamoto's games.
But what struck me in MI was how much text was necessary to explain the basic gameplay. It's daunting to new players, I think, for a game to need much explanation. However, once I launched a quick game and saw that what actually occurred on each turn was relatively simple, I finally got it. Minutes later, I understood (nearly) all the quirks of the game, and how to succeed. And obviously by then I was HOOKED.
A simple way to convey this I think would be to SHOW players the game through a pop-up tutorial in an in-game experience, rather than have a page-by-page explanation. Example: Tutorial 1: select your main planet. This will show how many ships are docked in the planet (click). Tutorial 2: drag the ships to another planet... etc.