Oh, that happened with one device and one app? You did not install the with a different app-id ?

Can you debug whats in the result:
https://github.com/aerogear/aerogear-unifiedpush-server/blob/master/push/sender/src/main/java/org/jboss/aerogear/unifiedpush/message/sender/GCMPushNotificationSender.java#L146

perhaps there is a different status for the tokens ?