How did you obtain the two messages id ?
From your description I strongly suspect it's a client app or configuration problem.
The notification with "a square white block for an icon" is likely the notification generated automatically by GCM or FCM.
(the white square is actually your icon in black & white)
Things you should check:
1. you are including only GCM or FCM, not both
2. your manifest only has 1 broadcast receiver for com.google.android.c2dm.intent.RECEIVE in the manifest
(if you are using FCM this broadcast receiver is automatically added by the library, you should not add it yourself)
3. check the logic in onMessageReceived(...)
also: test it by sending the message using the FCM api (with CURL or Postman) instead of using AWS SNS