Outage in St Louis today too. I was on a call when the iPhone dropped the call. I tried calling back over and over, but the call would not connect. So I picked up my home phone (land line for you youngsters) and called my friend back. He said "Let me guess, you are on an iPhone aren't you?". I sighed and said yes.
But, I got on the AT&T chat support on the website, and was told by customer service that 7 towers were down in my area. Jennifer Lopez (this was apparently the CS reps name) asked me to power my iPhone down one more time, even though I told her I had done this several times already. I did, powered it back up after about 2 minutes of downtime, and sure enough the phone made and received calls again. She said she did nothing, and that powering the phone off for the extended time forces the phone to search for a new tower on it's next power up. I don't really believe it, but my phone has worked ever since then.
And in my 15 years of being with Southwestern Bell Wireless/SBC/Cingular/AT&T, I've only had this happen twice to me.