Shapeways accepts VRML 2.0, no ZPR yet. Colors can be stored in the vertices or a texture map, but in your case, with flat colors, you are looking for vertex color only. Vertex colors will eventually be transferred to face colors, so color boundaries will not be maintained.
You can also color your STL in Meshlab and Output a VRML. It is common to have to re-scale the file anyway, since VRML units are always in meters. You can do both in Meshlab.
Simple Coloring: Filters>Color...>Vertex Color Filling
Rescaling from mm to meters: Filters>Normals...>Transform:Scale, Enter 0.001
Then (important) Filters>Normals...>Freeze Current Matrix
Save as VRML (*.WRL)