We ran into a similar problem with our Flex Viewer, returning a similar error code. It turns out our problem was the map used to create the map service was modified to include a join on the layer being searched on, and then the service was republished. Because of this change, the fields configured in the Search Widget need to be reconfigured to indicate which table was being searched on, such as seen in the example below.
Instead of our old configuration: <field name="PARCELS.APN" alias="Parcel Number" />
With the join we needed this: <field name="PROD_SDE.DBO.PARCELS.APN" alias="Parcel Number" />
Once I made this change the search tool worked perfectly again.
Brad Findlay
GIS Analyst
City of Rancho Cordova