Perhaps try to run the tool from the GP service's REST endpoint: if it fails here, examine the GP service. If it succeeds, the problem is in your client app.
You might also want to look at client logs (I believe this is available in the latest Flex release) and ArcGIS Server logs.