I had this problem when I first swapped to my GS2 from an iPhone. My wife and roommate were still on their iPhones, and they would send me pictures without problems. We found out the issue was with iPhone screenshots, not the pictures. Since the camera photos are .jpg files, they're actually quite small and don't really need to be compressed to send via MMS. The screen caps, however, are .png files, which are uncompressed on the iPhone. Since the iPhone can send and receive png files via MMS, there isn't a limit to what they can send and receive. I've noticed that any time I send a picture via my Android phones, they send a compressed copy that is reduced in size compared to what an iPhone sends.
I've never really found a fix, but after I started using alternate messaging apps (Handcent) I haven't received the error message. I think it may have something to do with a set limit size somewhere, but I don't know exactly what is causing it. My theory on the whole situation is that AT&T determines what phone you have based on your IMEI, and if it's not registered in their system as being able to handle excessive MMS sizes, it blacklists your phone from being able to receive messages over a certain size. Back in the pre-smartphone days, if an MMS was too big you got a text message from Cingular/ATT that prompted you to enter a code on a website to retrieve the picture, but I haven't gotten one of those since my old Motorola SLVR.
Nexus 4 - Stock 4.2.2 / Rooted
Nexus 7 - Paranoid Android