OK, I was facing the same annoying error with Maaloo Outdoor. Probably it was free in the past but became a paid app. Now, what I did and what worked for me: I went to the official windows phone website, logged in, searched for the affected app in the searchbox at the top on the right and simple bought it again. Don't know if my account gets charged, but the app is great and if it was free before, I can live with that...
Perhaps this will work for you too.
Best,
Stefan