I have the same problem with mine now (also livving in germany btw). Just the restart procedure doesn't work out for me. I will try tonight if it makes a difference to switch the wireless connection off before you do the restart because i didn't switch it off.
I have already tried to switch the carrier by pressing 311 in the setting menu but O2 3G and O2 GPRS and vodafone just produced the same error.
I hope your hint with the turn off of the wireless connection maybe brings a solution or i will also have to get a new device.
At least i can still read and transfer by USB is no problem. Only disadvantage is that i would have to pass on my newspaper until the new device arrive
Strange thing is i can use the Amazon shop without any problems and also wikipedia works as it should work.