FYI: I was using Contact Form 8 (the fork which fixed issues with checkboxes) — it has been abandoned in terms of development, and is not compatible with WordPress 3.0.
I have switched to Contact Form 7 2.3 and the issue has been resolved.
I will note, however, that my tables and graphic finesse doesn’t work with Contact Form 7 which is annoying.