Didn't you do any usability testing? It seems to me that most of the problems you encountered would have been caught if you had.
Here's an example.
Referring to the "tap an empty tile to drag around" section of the post.
This step was added because a lot of our testing revealed people wanted to move around the board but didn't know how. The problem was, we didn't test that tutorial step extensively enough.
It's hard though, we're independent developers making our first game. We have limited time and limited budgets, so compromises need to be made, otherwise instead 3.5 months of development turns into 6 or 12 months.
One mistake is we talked often with our 15-20 regular testers so most feedback was confined to regular gameplay, not on-boarding.
Really need to continually bring in new people on an ongoing basis that had never seen the game before. We did this to some extent but there's always more that can be done.
That said, we would pay a lot more attention to the on-boarding next game. I was quite happy with our tutorial so it's frustrating we left holes and fell short.
As Quentin said in another reply, one big mistake we made was that a lot of testing was with a beta group that had played the game dozens of times before the tutorial was fully fleshed out. Huge mistake! Another mistake was watching someone play it for the first time where we were in a position to coach them. We should've been silent and seen what they did. Easy to spot the issues in hindsight!
Check out the 'discount usability' movement. Much of it is written for web / mobile development but the principles are pretty much universal and can be applied to both game design and/or interactive learning aids (in your case the tutorial).
If nothing else read up on how to run a usability test. Without even being an expert it will help you get much more out of your testing.