Ah, I was planning to revisit this after I found the solution for my particular issue, but it must have slipped my mind!
As I'm completely new to designing 3D stuff to print, I followed the advise I read somewhere to always design at the scale you want to print, so I did not have the same issue as he6agon reports. After exporting my design from Blender I did open the resulting STL in FreeCAD to see if it looked sane and it did, including its location relative to origin. What I did not check at the time was if the scale was correct, and it turns out it wasn't.
Long story short: I got the error because the scaling in my STL was off a thousandfold: what was millimetres in Blender were micrometres in the exported STL. Still no clue why, other designs did not have the same issue.
Given he6agon's story, it seems like this error occurs when Shapeways can't find a suitable object to print (either by it being way to minuscule or by being out of scope). Checking the model after exporting is key, including paying attention to the units when measuring the model for size
Besides FreeCAD, I used
https://www.viewstl.com/ to check my exports and to figure out the solution. The corrected design (scaled up to metres in Blender, then exported again) printed beautifully!