make me think the app is offering a phone or travel service
The two things people immediately see when browsing apps is the name and the icon. Given that the name has "War" in it, and that they're likely browsing a games category, I'm not really concerned about that.
on my i phone none of the apps have a transparent background
The standard does seem to differ between iOS and Android. What about using #7 for iOS and #8 for Android?