Someone can easily change contacts by opening the Contacts app or just using the phone app. Because you have iCloud enabled, this will sync all those contacts to the cloud. However, in order for it to sync to iCloud, it must have (had) a interent connection.
The other way for someone to change contacts would be if they knew your Apple ID password. It sounds like that is not likely in this situation, but it would be possible. For good safe measure, I would log in, and change your Apple ID password immediately. That gives you hopefully another safety buffer.
I would immediately also go in and try to locate and/or lock the device (again). It is very easy to turn off FMI services on the device (note that if they were to do that, they probably would have wiped the device already or done something similar. Still faster may be better for you). If you can get a location from the phone (log into www.icloud.com, select Find my iPhone), you will likely be able to lock it right away. If you can't get a location, it will try to lock it next time the device comes online. By the way, if you remotely wipe the device, you will no longer be able see or lock your phone. When you lock your phone, make sure the Email when Found switch is set to On. (I just tested sending a message to my iPhone in airplane mode. When I turned Airplane mode back off, it immediately sent my "Test" message and emailed me that the device had been found.)
It would likely be a very good idea to get as many of the contacts as possible and give them to the police. Depending on the type of person that stole your phone, this could be very helpful. You could also look through and see if any of the contacts have your iPhone's number there. That very well could be the thief's name (they would have to do this to use Siri efficiently).