One reason could be the limited capacity of 2G networks. Usually a GSM basestation consists of 3 sector antennas (each covering a 120° angle) and each of the sectors can have not more than 4 channels, which again have 8 timeslots each. That means there are 3 * 4 * 8 = 96 timeslots at max, of which some are required as control channels (BCCH, SDCCH, etc.) reducing the total of possible voice calls per basestation to 90. So a GSM base station can handle not more than 90 voice calls.
Usually your phone won't be able to connect to all sectors, as at least one is oriented in the opposite direction. But on the other hand the cells (= the area covered by such a sector antenna) overlap, so your handset should always be able to connect to a neighbouring cell in case there's an overload on the serving cell. Further most European network operators have frequency spectrum at 900 and 1800 MHz of which the latter is used on top of 900 MHz cells in order to extend capacity. Anyway, wherever you are, the number of available channels/timeslots is limited, especially on trains, where due to attenuation the signal of many neighbouring cells will be too weak and only few cells can serve your handset (especially those at 1800 MHz, which suffer from the physical disadvantages of the higher frequency).
Now while a voice call requires just a single timeslot, an EDGE data connection with full bandwidth (236.8 kbit/s) occupies 4 timeslots, which corresponds to the capacity of 4 voice calls. So a smartphone downloading something at full speed consumes 4 times the capacity a voice call would do or in other words just 8 smartphones downloading at full EDGE speed could use a cell of 4 channels to the full.
Now imagine a train with several hundred passengers coming along, some of them making voice calls and some surfing on the web. They can quickly overload the network.
Of course network operators won't permit few heavy data users to practically block their networks and so they priorize voice calls over data and dynamically assign the number of timeslots available for EDGE, which results in fewer timeslots available for each EDGE-connected user and so fewer bandwidth.
This said I believe the higher smartphone penetration in the economical stronger countries in combination with the limited capacity of 2G networks (and the inability to use most of the GSM1800 cells while riding a train) cause the inferior user experience you see in Germany.
E.g. in Bulgaria I always get data rates of 150-200 KBit/s through EDGE, while here in Germany I rarely see rates above 100 KBit/s and in urban areas (indoors where you don't get a 3G signal) I often get even less.
Further consider the more difficult topographical properties of Germany with hilly uplands and the higher costs to build additional cell towers.
But there's hope for improvement due to the LTE networks (4G) on 800 MHz being rolled out in Germany, which will have much higher bandwidths than UMTS (3G) and have a very good signal dispersion due to the low frequencies used. The imminent roll out of 4G networks is also a reason why operators invest only little in the existing 2G and 3G networks here.
Another problem here in Germany concerns eplus and O2, who were awarded GSM900-licenses only in 2006 (earlier they used only GSM1800 besides UMTS2100). Further their 900MHz spectrum is in the so-called E-GSM band (E stands for extended), which uses frequencies below the original (P-)GSM band (P stands for primary). Allthough every GSM900 phone produced since 2005 supports E-GSM at the time when eplus and O2 got their new spectrum many trains were already equipped with repeaters, that did not support those E-GSM frequencies and so they did not work for eplus and O2 clients at all. According to
this detailed article on Wikipedia Deutsche Bahn intends to replace those old repeaters until 2011 and 1495 train cars will be equipped with E-GSM capable repeaters. By September 2009 half of them had already been installed.