What to do when the initial design isn't fun?

My thoughts are that you are doing everything right. You make a plan so that you know what to implement. Hopefully during that process you try to think about potential problems and solve them before you ever start coding. Then you code up the game according to the plan and test as you go. The most important part is to accept when something isn't fun (as opposed to just pushing on regardless). If it isn't fun you tweak it or change it until it is or you bin it and come up with something else to put in its place.

The one thing you need to be careful of is that incomplete or incorrectly tuned features can distort the overall gameplay.

Refine your design. You can't realistically expect to get -everything- perfectly planned on paper. Implementation in software usually deviates sleightly from design no matter who you are. Let me use Blizzard as an example. Their original Starcraft idea looked too much like Warcraft II, except with purple ground. It received lukewarm and hostile response and so they completely changed the look and feel. In another example they were making a 2d cartoon adventure version of Warcraft. It sounded good at the time, but realistically it wasn't going to be a hit and just wasn't going to be a ton of fun. They completely trashed the idea even though it was nearing completion.

Basically, if you can afford not to settle for a not-fun game, don't settle for it.

If you have playtesters (it sounds like you do), you should ask them what they think would make the game more fun. Try to figure out the difference between the game that you and they imagined in their mind after hearing the concept / reading the design doc, and the actual game.

Also, if you tend to be critical of your own work, it can be useful to take a break for a few days and not play at all, then come back and look at it again with a fresh start. Too much of anything will start to get boring.

I think the planning stage is there to spot the obvious problems and avoid them, but there's things you just can't spot in that stage. Testing always brings more issues (and idea's) to light.

Maybe you'd like to read some game postmortems. I read the one from Wik and the Fable of Souls recently (on Gamasutra), and they only implemented the core gameplay elements about half-way down. Luckily, as their old mechanics sounded like a lot less fun. :)