How do you get Market to work when Android is Unable to Access Android Market?
I don't know if this helps, but with SFR, in France, I have nearly the same issue ; i can't use the market OTA (unless I use WiFi).

It is due to limitation from the carrier ; perhaps rooting the phone could help to get rid of that limitation.