Sorry I didn't get back sooner, I've been out of town and then terribly ill...
We published a service with the test data and get the same error.
It LOOKS like I've got Service Pack 1 (the Patch Finder tool seems to say I have it and my build number says 10.1.1 (build 3143)).
This server ONLY has the ArcGIS server, Web Adaptor and IIS on it. NO desktop arc gis, NO SQL, NO anything else. It was a fresh build a few weeks back, so there's very little extra on it and it's only ever had 10.1 on it.
So, here's my guesses as to what I'm missing (things that are probably installed by default when other products are installed) and maybe you can confirm or otherwise my suspicions and point me in the right direction.
1) I'm missing a .NET update of some sort.
2) I'm missing a c++ redistributable of some sort.
3) I'm missing some other plug in or supporting dll of some sort.
Thanks!