This is what I have found:
The way is seems to work is by stopping the New Mail "Ringtone" and playing a sound file. This means that the volume of the notification is not the same as your ringer volume but the sound (Music & game sound effects) volume.
So my game volume was turned all the way down. I have turned it up and now it works. Hopefully the developer can find another workaround for this.