A co-worker of mine encountered the problem "The base table definition string xxxx is invalid" yesterday.
In this particular case, he diagnosed the problem to be related to installing custom features classes and class extensions on the server which referenced a missing DLL.
This implies to me that this failure message is very generic and is simply saying that the server has some type of configuration issue. It would be helpful if ArcGIS Server provided additional/better error information.