Using pieces from the forums here I have found a solution to my original problem. Since I couldn't find a post that duplicated my problem exactly, I'm documenting it here.
I upgraded from 3.2 to 4.0.1 on a Debian system. A few days later I did a hardware upgrade, during which there was an accedental power failure to the old system. Upon rebooting, Zimbra was in a half-functional state. Tomcat started and all users old messages were visible. Sending new messages failed each time with the same java exception and no new messages were being delivered to the user's mailboxes. Instead they were getting stuck in the postfix active queue.
I found a post addressing incorect root permissions after an unclean shutdown. Resetting the permissions manually on the index directory fixed sending new messages.
Then I found some posts about the /opt/zimbra/libexec/zmfixperms command. Runing this as root appeared to fix the problem, yet the active queue was still not being delivered. Neither were new messages.
After more reading, I typed postqueue -f as the zimbra user and the active queue flushed, delivering all old messages. New messages were also delivered.
The frusturating part about this problem is the postfix errors didn't make the source of the problem very obvious. Here's the sequence to run after your Zimbra server has shutdown uncleanly:
# /etc/init.d/zimbra stop
# chown -R zimbra.zimbra /opt/zimbra/index/
# /etc/init.d/zimbra start
# su - zimbra
zimbra$ postqueue -f