Does Find My iPhone still work with a SIM block? My iPhone was stolen this morning. I've had the SIM, but not the IMEI blocked.

It was turned off immediately by the thief. I'm hoping that, as it's got the iOS 7 beta, they'll be unable to crack it and confused, and might turn it on. Will Find my iPhone still work if the SIM is blocked?

The network support guys assured me it works on a lower level than standard 3G internet access. Is this the case?
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.