Ubercart shipping quotes silently fails on server migration
Ok, I eventually traced the issue back a module called "UUID", which is required by Node Export.

Disabling UUID module solved my issues. The errors in the rules UI (admin/config/workflow/rules) simply went away.

Would love to know more about why this is. I don't need node export at the moment so it doesn't matter to me.