Same problem here in the UK using vodafone with pecan.

I switched to using haze which comes with the pidgin protocols aswell ("Pidgin protocols plugin for conversations and contacts" in app manager) and its working on 3g now.

problem is, you may get duplicates of your contacts.