The problem is you "lost" you iphone 5. Unfortunately you needed to sign off imessage first with the iphone. I know it's not practical (since you lost the iphone). But it's common knowledge this is a severe problem with imessage.
I figured this out the hard way when I constantly was...