I have just worked through this problem so here's a solution for anyone who finds this page in future.
There are two approaches to increase the volume: either modify the AudioFilter.csv file on the phone, which contains the volume limitations; or upgrade the OS to Gingerman (the open source mod of Gingerbread) which has a lovely DSP app built in, which can be used to make the same edits graphically.
Both options require rooting the phone first.
I didn't quite make it to fixing the headphone level with the csv file, although I got the speaker under its control -- at that point I switched to installing Gingerman, which I think is the better solution. My phone now has full volume so I can hear my music on the train.
(The important thing to note is that when rooting, use rageagainstthecage but realise that it is nondeterministic, it relies on exploiting a race condition so might only work one in ten attempts. Just keep trying until it gets you in.)