my wife had the same issue with her iPhone 4, we got a new micro sim from att, a few weeks later the no sim message reappeared (sporadically) so we just swapped out the device at the local apple store - 2 days before the warranty expired!! - the upshot of it was the replacement device from apple carried a 90 warranty, so we gained a free 88 day warranty 🙂
Anthony