To the left hand side of the screen, there's a long, silver button (around 1.5cm in length).
If you tap the lower end of that button a couple of times (whilst your phone is in use), you'll notice a decrease in volume.
Is soundcheck on (on both your iphone and itunes)?
There's also a volume limit setting in the iPod settings on your device.
If you've got all your volumes at the lowest setting, I'd argue that you have either got your mp3 gain through the roof, or you've got some sort of amplifying headphones.
There's no way the lowest sound setting could be an issue.