In the limited sense that Find My Phone needs a data connection, blocking the 3G (or whatever G) data connection via the carrier would prevent a remote erase / location while the device is outside Wireless range of a known hotspot.
Find My iPhone relies on a connection to the Internet, through any medium. Wi-Fi, cellular or cans with bits of string. If the thief connects it to the Internet, then it should be picked up by Find My iPhone, even if they don’t connect it via 3G.
If the thief turns the device on and connects it to the Internet, Find My iPhone will kick in.
You can check with Apple whether your Find My Phone enrollment should prevent activation of the device if they restore it to factory settings. Anyone running the publicly released iOS 7 version would not need to block the SIM as the activation lock would prevent removing the Find My Friends association by preventing an erase / restore cycle.
Finally, the cell company still could locate the device by their cell towers whether the IMEI/SIM is blocked or not.