I use the default gain of 89.0 dB and my mp3s work fine on my computer and ipod. Can't say if there's some problem with playback on your phone or not. However, I can say that changing the gain mp3gain is a lossless process, so if you end up changing the gain too high, you can change it right back and have no problems.
You can use this program and itunes to change your songs to .aac