This happened some time ago, apart from what's attached to in the orginal message I can't offer anymore insight.
However upgrading from a basic license to the advanced made all the difference.
Thanks for the response Elliott.
It turns out that even though we had the same error message ours is a bug. We have ArcGIS Desktop clients at 10.1 and have published a 10.2.2 map service containing a mosaic dataset . When the user tries to load the 10.2.2 map service into ArcMap 10.1, they get the error "Could not add the specified data object to the map. Could not connect to the Map Server". There are multiple NIMs against this issue. (NIM099704, NIM103114, NIM104580).