How do I troubleshoot 3G connection on the iPhone?
Wow, tough one. Tough because there are many unknowns in this equation... 

No way to know for sure if China Mobile is not causing the problem by blocking, for example, the ports required to connect to the mail server. The only way to test this would be to change the port settings on both the server and the client, I think. In theory, it is entirely possible for them to block ports they believe can be problematic or some other reason, although I don't see how blocking standard mail ports would be problematic and help their customers...

Are other services functioning properly when on 3G? Like web-surfing, app updates, chatting, etc.?

It might be a case where your client needs to contact China Mobile and ask them for a little help troubleshooting this problem on their side, just to be sure it's not their network that's causing the problem...