There's an epilogue to the story: When Shapeways re-made the parts, the good news is they came back with a smoother finish (see previous photo). However, I tried to actually assemble these parts today, and the result was even worse.
You see, for some reason, the re-make was done as three separate orders, and the three parts arrived in individual boxes 4 - 7 days apart from each other. The parts - puzzle pieces - depend on being exactly the same size. However, because the parts were each made on different days (presumably in different batches, perhaps by different machines?) the tolerances were way off. They are designed to work with a tolerance of 0.1mm, but in this case two of the parts were actually around 0.5mm apart from each other. So yes, the surface was "smoother", but the interior surfaces required substantial sanding to work, and the result didn't fit together cleanly.
The original parts with the smooth finish (made in June) worked perfectly the first try. The "rough" parts made in December just required a light sanding to smooth the mating surfaces. But the remade parts in January required heavy sanding and ultimately did not fit well.
Moral: Make the same parts from the same batch on the same machine.