It could be a connectivity problem. I had the same issue. I called Sprint customer service line for help. They tried to reset my phone with out doing a "hard reset" but no luck. Eventually they decided they would send me a new phone. But I still wasn't ready to give up on my phone (I had so much info on my phone I didnt want to lose it). So I started looking my message settings again. I noticed that in the "Connection settings" all of the fields (Name,MMSC, MMS proxy, MMS port, MMS protocol) were empty. Of course, I didn't know what should go in each field, so out I frustration I decided to HARD RESET my phone(losing most of my info). After that, all the fields was filled and I was able to receive and send pictures messages. Just in case it happens again, I wrote down all the information in each field so I can enter everything manually.
I had the same problem: Unable to download message - Service Denied, I had my Sprint Hot Spot turned on at the time. So I turned off the Sprint Hot Spot and everything was fine, downloaded OK.
LMCELVANY-Are any of you using the WIFI connection on your device? If so, you need to make sure you disable WIFI and connect using either the 3G or 4G connection.