May or may not help, but try network mode = GSM only.
That worked for me after much checking/resetting my APNs with no luck following a new rom install on my Galaxy 580. Default setting was auto (ie GSM/WCDMA) but changing to GSM only seemed to get MMS working. Weird.
Ok I found a way to get it working, looks to be an issue with Telecom rather than my phone.
Using the same settings as specified in the sticky post and using the normal messaging or handcent app it would not download a message, on reading around other forums I saw a few people in the states having issues of their carrier shrinking down the images so tiny they could hardly see them, why? because the carrier did not recognise the phones user-agent which is sent to the carrier when trying to download a message.
so I downloaded someone's modified messaging app that allows spoofing of the user-agent in the options menu, I changed my to "generic android" and boom it worked instantly.
The fact that 2dgrees and Vodafone MMS would download without needing to do this, makes me think TNZ have some strict blocking in place to try and limit smart people like myself who bought their phone overseas for a third of the retail price here to prevent them from being able to use all the features of the phone.
Would love to hear an official comment on this issue..
Might have been a bit quick to jump the gun on TNZ, decided I wanted to keep the stock messaging app as it had a few features I needed and that i would just change the useragent in the file, so I decompiled the application and went to modifiy the user-agent in the code, seemed it wasn't set at all. so once I set it and reinstalled the messaging service mms worked all good.
so hopefully this thread can at least help someone in the future if they have the same issue, it would appear tnz are the only carrier in NZ that won't let you download an MMS if you don't have a valid user-agent set.