Android : Device Subscription Expired when trying to send Android Notifications

I keep receiving this error on our test application. I've reinstalled the app and watched it register the device. Then it pushed the device ID to the server. I deleted it off the server just to be sure it was correct.

For the device registering I'm basically using the Google example almost exactly. I only modified the store back end portion to send the ID to the server. I tried generating a new server key. I'm at a complete loss as to what to do. I've checked and rechecked everything.

I'm using the PushSharp library to send from the server. I've removed it and updated to the newest beta version and still get the same thing.

Since it's a device expired I can only assume it's sending to the server correctly and when I compare the device id to what's in the database it appears to be the same. Since the app pushed this id to the server right before I tried sending the message and I removed all other IDs so I know this device ID is good. Any help is greatly appreciated.