Stephanie's tool works perfectly. When I converted a bunch of my categories to tags using the category-to-tag converter in WordPress 2.7, a whole bunch of my posts were left category-less. They showed up as "Uncategorized", but this is NOT the same as the default "Uncategorized" category that WordPress sets up. These posts were left category-less.
Saved me a bunch of work. Thanks a lot.
http://wordpress.org/extend/plugins/assign-missing-categories/