iPhone 3GS constantly Searching... on 3G network.

This could be due to a problem with your iPhone's SIM card.

You can try placing your SIM card in your finance's Blackjack to see if the same occurs using your iPhone's SIM card with the Blackjack. If so, you can get a replacement SIM card at an AT&T corporate store and the store should be able to activate your iPhone at the store with the new SIM card, or you can activate your iPhone with the new SIM card with iTunes on your computer.

If this isn't a problem with your iPhone's SIM card and AT&T is unable to resolve this by resetting your line/number with your iPhone - this will require powering your iPhone off while AT&T does the reset, and since there was no change after restoring your iPhone with iTunes as a new iPhone or not from your iPhone's backup, the next step will be calling AppleCare or make an appointment at an Apple store if there is one nearby.

I am suddenly having this problem as of today, without having updated anything, and without anyone around me complaining of the same thing (I'm in a college, so there are PLENTY of iPhone users within complaining range).. It's been saying 'searching' for most of the day and will occasionally catch up and deliver a bunch of text messages to me, and then go back into 'searching'

I have had this problem for 3 weeks.
I have an appointment Saturday at the Genius Bar to see if I can finally get it resolved!
If I get a solution I will post.

!I am having an issue with my 3Gs iPhone where if it has ENABLE 3G turned on, I cannot make or receive phone calls most of the time. I have had this phone since last June, and never had an issue with it before.
I called AT&T and they indicated that perhaps there was a service disruption caused by severe weather (it was very windy the night before this started happening) in Boston area recently, but that if I enable 3G and reset my phone I should eventually have full signal back. That has not turned out to be the case. I have even restored my phone as a NEW phone and that still has not helped. AT&T also indicated it would not be the SIM chip as I have no problems if I disable 3G in settings.
Another weird thing is the signal strength is showing as full strength most of the time when I have this problems although when I disable 3G and then reenable it, it drops to nothing for a few seconds. I did the cell strength field test and had -90's which is good so I am at a loss. Sometimes if I turn phone off and then on again, I will be able to make a phone call or 2 before it resumes getting CALL FAILED messages, but it always is very short lived.

Could it have something to do with firmware 3.1.3? (Version is 3.1.3(7E18)?
Is anyone else in the general Boston area (I'm in Malden) having this issue?
If you have had this issue and resolved it, what did you do?

The phone has no damage, has never been hacked, dropped or gotten wet, and this problem just started out of the blue for no apparent reason.

I had my GENIUS appointment today. They did a couple of tests by plugging my iPhone into a macbook and both came back without showing problem. However as the genius was working with my phone he ran into the same problem with 3G and I had taken some screen shots showing full signal strength but unable to make a call, failure to send mms, and internet unable to connect, so he switched out my phone for a new one as I am still under warranty for another 3 months.
Make sure you backup your data and restore your phone as a new phone before going in to see a Genius, otherwise they may choose to try that process first and do some diagnotistic tests before being able to switch it out, and that can take up to 4 days.
Best guess by the Genius was that it was a hardware problem with the internal cellular antenna. He also recommended I get a new (free) SIM card from AT&T which I did (kiosk was in same mall)

So bottom line...if your 3G is messed up, make an appointment with Apple Genius.