Does changing the password for Apple ID make iCloud and Find My iPhone stop working? My phone has recently been stolen. I have been trying to locate it. I had previously set up the Find My iPhone app and after the theft, I have changed all my iCloud and Gmail passwords.

Can the person with my iPhone change it over to his iCloud account so that the Find My iPhone app won't work for me?
You need the original Apple ID to deactivate the Find my iPhone function on the phone.
If the person who has it has put it on DFU mode, and its iOS version is 7 or higher, he will need the original Apple ID to reactivate it.

You may wish to put the phone on "Lost Mode", that will put a message on the phone lock screen with information of your choice.  

It's important to know that downloading the Find my iPhone app is not the same as enabling Find my iPhone.  

There is a detailed explanation of the functionality of Find my iPhone on this article on Apple Support