Hi there,
I also run into this problem from time to time and it can be really painful to solve it.
What Bill described is a workaround for the problem that - in my opinion - should be used as the last option! Before flooding your texture memory you should really think about what causes this problem. So first off find out how many "physical" vertices are on one material.
IF you have a massive 3D structures and you are indeed exceeding the 65k mark just with the basic geometry, you can use the work-around technique as described above (my Bleriot now has almost 200,000 vertices - so it is really not hard to reach these limitations).
But it also happens that your number of vertices is significantly LOWER than the 65k material-vertice-limit and you still get this error and in that case it is difficult to find the actual problem - but worth it.
I ran into this problem with my Electra. One weekend I decided to redo the R985 engine and after three days work the new model was ready to get exported but I just got the 65k-error message. The first thing I did was to add a new material, as Bill suggested and solely assigned this material to the engine. Export -> same error. The engine itself had just about 5000 vertices and even when I deleted everything EXCEPT the engine, it could not be exported.
So here is what happened: In addition to the "geometry-vertices", the exporter creates additional "uvw-map-vertices". If you don't map your parts wisely, the amount of additional vertices can go nuts. For instance: if you map a part in a way that polygones cross the "border" of the texture map, additional vertices are generated to virtually split up the faces.
So here is the solution: find the part that causes the problem. Check the "physical vertices" of that particular part. If the physical vertices exceed 65k you really should change your modeling style

If not, try remapping the object from scratch and export again.
Still no luck? Either go with Bills workaround, or better: start modeling the part again. In the end, by clone-creating a new material you are unnecessarily using up memory space thus decreasing the performance.
Cheers,
Vitus