After a week of failed attempts, I finally got rid of the "error while searching for networks" message on my G2! I had brought a T-Mobile G2 from the US and wanted to use it with my Vodaphone SIM card here in Greece. I had already had it unlocked by T-Mobile, but after that whenever I would try to scan for networks it would just say "Error while searching for networks" and never see nor connect to any phone networks. After talking for a while with T-Mobile "android specialists", they determined it's a problem with the firmware, and I'll have to get the device exchanged next time I come to the US, hoping that it would be fixed by then.
But today, my friend kargig found a wiki with a solution:
This page describes how an added "security" feature is actually preventing your phone from connecting to networks, despite being "unlocked." The fix, as described in detail at that link, involves rooting your phone and then running a program called "gfree."
Of course, as this is altering your phone's firmware, it probably voids any warranty you have and involves a certain level of risk. For me though, the process was very smooth (and easy!) and worked perfectly: I can now connect to my vodaphone network on my T-Mobile G2, as well as see the other networks available!
Hope this can direct other distressed users with the same issue, so they can have as happy a day as I am :)