The problems is not with the phone. In the US it occurs with 3G SIM cards from Cingular.
For a very good discussion of the gibberish problem, go to:
http://treo.discussion.treocentral.c...d.php?t=131154
Read the posts from Electro-Tether on page 5. He recommends getting a new SIM card from Cingular with model no: 73000 G 3021 to replace the existing model no. 73000 O 4021.
I have had the same problem. Cingular said to go to a Cingular store and get a new SIM card for free. Store only had the 4021 cards, which I already have. Cingular is now mailing me the 3021 card. Will let you know if it solves my problem.