I was seeing this issue reported here http://drupal.org/node/455888 for some orders and not others. Very strange since I could find no pattern. I was able to replicate the problem simply by going to "view invoice" and trying to email the invoice to myself. I would get the error on some invoices and not others.
It turns out that the problem was in my mime mail settings. I had not checked the box for "Use Mime Mail for all messages." When I checked that box, all of my emails of invoices went out.
This problem was of course affecting the conditional actions emails since those invoices are sent to both customer and admin.
There must be something in those invoice templates that requires that one use mime mail. This explains why my contact form worked fine--but email of invoices were intermittent problems. I've seen other users describe intermittent problems with this, and I wonder if they should check this setting too. I will also post this comment over at Ubercart since I can't ever tell if Ubercart is supported here at drupal.org or over at ubercart.org.