Not sure any of u face this problem before
My iPhone 3Gs always how NO SERVICE under the carrier there whenever i on my 3G for a while, my colleague face the same problem as mine.
We are both updated from 3.1 to 3.1.2
What i do is every time i need turn it off and on back again and only will found Maxis signal, Really headache of this issue

I found that this issue is been discussed at apple iphone forum as well