Been having the same problem with the marketplace only been able to download via wifi. Just got round it by going into
settings- mobile network- and turning off the data connection and the 3g. Wait 5 seconds and then turn both on.
Back into marketplace and download a free app.
This worked for me.