In the FInd/Change, you can tell it to search all of a Selection, Story, Document, or (going from memory, here) All Documents. It sounds like you have it set to Story, and you have one story (one unthreaded text frame) per page. However, setting it to Document will allow you to change settings at one fell swoop throughout the document.
Lifesaver! I didnt even know I could do a find/replace for languages. Done and done!