Wifi macht da keinen Unterschied. Internetverbindung ist Internetverbindung. :-)
Es könnte an der SIM-Karte liegen. Schweizer und Österreicher haben bisweilen noch mit Einschränkungen beim Market zu rechnen. Dafür gibt es eine
App namens
http://www.android-hilfe.de/android-...t-enabler.html
Kannst du denn sonst ganz normal surfen? Also beliebige Interseiten aufrufen? Und diese Fehlermeldung kommt nur, wenn du den Market öffnest?