If you are preforming a query on a joined layer than you need to ensure you are using the full joined field name like table1.field1. Also ensure that you do not have the Shape and/or Objectid fields hidden in the mxd/msd that the mapservice comes from.