I had the "Network search" problem (never connecterd). I tried everything the radio reset, drain the battery manually and the same problem was there.

I update GPRS again to v.1.1.1 (Europe) and voila! My Treo is working again!!!.