I ran into the same issue when I was making a puzzle. The solution is to use a small end mill (.0625 inch works well) and to be positive all your cuts are done on the outside of the lines.
Here is my original post and discussion about making puzzles
What software are you using?