My first thought, reading the question, was you were blowing up the image too much, but that does not appear to be the case looking at the image you have of the app.
Second thought is color palette, but with black as one of the colors that is not rendering correctly, this is not as likely.
If you can fully rule out the two above, I am currently stumped.
As an experiment, you can try other graphics formats, but PNG should be fine. I will have to think it through some more to come up with a better answer.