Building Instant Search Error

I am trying to build an instant search for a large layer, and I keep getting the following error:

 

"Current status - Error!

 

HTTP Error - The remote server returned an error: (504) Gateway Timeout. Encountered at XXX for URL XXX..." 

 

 

On ArcServer the "Maximum Number of Records Returned by Server" is set to 5,000, and I have tried stopping and restarting the map service. Other layers in the map have instant search working fine. Any ideas on other possible causes for this timeout and failed instant search?