This is actually not a problem with Avast but with Google Cloud. I researched and found the following:
"Good news. Both user are back online hand happily registering their devices. For User #2, all it took was rebooting the phone. Use #1 had tried rebooting the phone multiple times with no success. But they had are app installed on the SD card. Once the moved it to internal memory, and rebooted the phone, everything started working.
This is the second time I have heard of problems with C2DM that went away when the app was moved from the SD card to internal memory."