I finally got it worked out. As it turns out, the plan that I was on (EasyOwn) is just WAP. I upgraded to a new one called M-Zone and now it uses GPRS and everything works. This is after quite a few calls to China Mobile and asking around at various shops that sell SIM cards for the various plans. It seems that a lot of people didn't know the difference.
So Gurdeep.Singh.Mander hit the nail on the head. When I asked that question specifically, they didn't know. So I took a chance and upgraded my plan and 'presto'. Happy as a clam.