Frank,
Thank you for providing the data. I published service on ArcGIS Server for Java (v10 + SP2) and ArcGIS Server for .NET (v10 + SP2), tested with Route Sample and did not came across any error. Please try to intercept the request/response being sent from app to server to diagnose this further.
Regards,
Nimesh