I wonder if it has to do with the phone? I've been sending photos and videos through handcent with no issues since I installed it Monday night. I did notice that it has to compress the items to send, maybe it's not compressing correctly and fails?

Try uninstalling and reinstalling. I checked the handcent forums and they have a fix that might work if you want to try it.

http://bbs.handcent.com/viewtopic.php?f=5&t=2269