Maybe a little side-demo shipped with the game that a first time player can use to figure out the workings of the game. A five minute tutorial like this beats the heck out of a huge paper manual. After you've done the demo once, just go straight into 'New Game' from then on out.
They could release a short free demo-tutorial-hybrid, and so they could explain the key features and win new customers at once.
