C2DMは便利なのですが、間にサーバをかませるのでトラブった時に原因追求が難しいです。
というわけでハマった点2点。
・C2DM は端末もGoogleアカウントを持っていないと通知が来ない。
まあ当たり前ちゃあ当たり前なんですが。試験端末に通知が来ないのでどうしたかと。
・Android3.1以上の端末ではアプリケーションを強制停止してしまうとC2DMが受け取れない。
こっちのほうが問題。日本語での解説が見つかりませんでしたが、確かにGalaxy Nexusではアプリのプロセスが起動していないと通知が来ません。
http://stackoverflow.com/questions/7433129/c2dm-reciver-doesnt-work-when-app-has-been-killed
broadcast intent callback: result=CANCELLED forIntent
Receiver package not found, unregister application [package] なんて言われます。←検索用