There's a little more discussion about this problem in
this thread, including input from Shapeways.
I'm afraid the only solution I've found has been to reduce the resolution of the model. Once I'd done this, the model uploaded fine, but this may not be viable in all situations.
One other alternative may be to convert the vertex colouring into a texture. Meshlab will do this for you using the following steps:
1. Load vertex coloured model into Meshlab (in my case this is a ply file).
2. Select "Filters > Texture > Trivial Per-Triangle Parmetrization".
3. Click "Apply" (you may need to adjust the Inter-Triangle border or increase Texture Dimension if this generates an error).
4. Close the dialogue.
5. Select "Filters > Texture > Vertex Color to Texture".
6. Click "Apply" and close the dialogue.
7. Export the model in a suitable format.
Although I've successfully imported the results into another graphics package, I've not tried this with Shapeways, so I can't say whether this will actually solve the problem. Also, I experience some loss in the quality of the colouring when doing this.
Personally I'd be interested to hear if you have success with this or any other method.