this troubled me for some time and all the settings were correct (vodafone uk) but re-entering exactly the same solved it, don't know why though? saying that i have no problems in last 12 months
do you get a sms telling you that you have been sent a mms and to retrieve goto some site and enter this pin.
sure i read somewhere that the carriers sometimes stops mms and a call to them to re-instate it.