Comment by sunsu

I had this same problem and recently solved it by - putting my sim back into my old iOS phone. - reactivating iMessage on the old phone WITH the sim inside of the old phone - wait to make sure the phone fully registers with iMessage servers - deactivate iMessage WITH the sim inside the phone

After following these steps, I'm not problem free. I had tried many times before to reactivate/deactivate iMessage, but never with the sim back in the device.