Sent from my SAMSUNG-SM-G900A using Tapatalk
Did you have multiple Google accounts on your last phone? Make sure you are downloading the app with the same account that you originally made the purchase with. I had multiple accounts on my S3, then when I got my S5 I only put one of the accounts back on and was getting this error for a few apps even though GPlay said "purchased". You might also want to check that the date and time on the phone are correct.