Did it happen after updating to 5.1.1.?
If it's a carrier locked (AT&T) iPhone, use another AT&T SIM card OR if it's carrier unlocked/factory unlocked iPhone use a SIM card from a different compatible carrier to see if the "no service" issue gets resolved; if it does then replace your current SIM.