I finally got iMessages to work! What you have to do is downgrade (DO NOT RESTORE) ((manually downgrade)) to the latest firmware for your device. After that you should restore to the most recent backup you have on that firmware. ( ex. 4s was running 6.1.3 so I downgraded to that then I used the most recent backup I had on 6.1.3) Then simply upgrade to iOS 7!