As soon as I got my Samsung SCH-i760, I configured the phone to use the DNS servers from OpenDNS. Everything seemed to be working fine, and web browsing seemed faster. A while later, I tried sending an MMS message, and it just didn't work, but an error messages was shown.
I finally, got around to tracking this down today. It looks like Verizon uses a MMS server that has a host name that only resolves from inside the Verizon Wireless network. So OpenDNS is not able to resolve this hostname.
Once I switched back to the default servers I was able to send picture messages again.