Yesterday I replied to some people who suffered from data loss, had deleted the game and only reinstalled it after the new update was out. In this case the game has no way of knowing that you actually have suffered from data loss as there is no evidence (a save file) of it left.
We discussed what we could do about it and arrived at the same solution I hinted at in comments. Upon logging on to OpenFeint, the next update will check if you have an online achievement but no corresponding local achievement. If so, you will receive the cost of the character in kills. This ensures you get the correct amount of kills. You can then use those to unlock any characters you want.
Hopefully this will remedy the issue for the rest of you out there. We will look into restoring your local scores from OpenFeint in a later update. If you see any loopholes with the kill restoration scheme (being able to choose different characters than you did before does not count), please tell us in the comments. Cheers!