Hi, die Antwort ist zwar etwas spät, aber..
das Problem hatte ich auch noch unter Debian Lenny mit Gnome und unter Ubuntu Jaunty Jackalope und dem Provider 1und1.
Lösung: Habe aus Verzweiflung den Thunderbird installiert, danach war das Ping-Problem in Evolution weg o_O
Habe aber nach der genauen Ursache noch nicht tiefer gegraben.