初回起動時にGCMメッセージを受信する現象

GCM Helper LibraryはC2DM終了に伴い使えなくなる疑いがあります。
アナウンス
コメントでは中の人がGCM Helper LibraryはGCMを使っているよ(=C2DMではない)とありますがアナウンスと矛盾しているので早めの移行をオススメします。

古いGCMのライブラリ(GCM Helper Library)を使用していると初回起動時にGCMにregisterする際に下のようなデータのメッセージを受信するようになってた。

extras=Bundle[{CMD=RST_FULL, from=google.com/iid}]

上のメッセージをググったらStackOverflowがひっかかった。
Weird push message received on app start

This is intended for the new GCM APIs, and it will cause your InstanceIdListenerService implementation's onTokenRefresh() method to be called, where your app should obtain all its tokens again.

Unfortunately, if you are writing your own BroadcastReceiver, these messages will be unexpected and may cause your app to crash. The right thing to do is to filter on the "from" field, and if you see one of these messages, to register again with GCM as your tokens may be invalid.

Google Play Services SDKを使う分には全く問題ないす。