If you have a registry editor available, go to HKCU\Software\HTC\Manila, find the entry named InternetSearchURL and change the data from
Code:
http://www.bing.com/search?q=%s
to
Code:
http://www.google.com/m?q=%s
After making the change, try using the search box. If it doesn't work, soft-reset and try again and it should hopefully work then for you.
EDIT: If others want, I could make a cab of this for easier installation/use