One further thing I just realized,
This isn't only during checkouts, as some of these errors have referrers from external sites such as Google:
[Tue Apr 28 21:17:03 2009] [error] [client 67.78.57.216] PHP Fatal error: Call to undefined function uc_order_state_default() in /home/sites/bloodshotrecords.com/www/pages/sites/all/modules/ubercart/payment/uc_credit/uc_credit.module on line 193, referer: http://www.google.com/search?hl=en&q=Subject+of+the+site+&aq=f&oq=The query leads to a node that is just a regular CCK type, not part of the store. I can't get the message to trigger by following the link myself, but it's happened for other people on this link, as well as several dozen others.