Ok, I found the problem, and a solution.
It appears that if there's a problem with the taxonomy table, WP will return an object instead of the intended string. So, for example, instead of using this:
$cat_parents = get_category_parents($cat, TRUE, '' . $delimiter . '')
We have to use the following to avoid PHP throwing an error:
echo is_wp_error( $cat_parents = get_category_parents($cat, TRUE, '' . $delimiter . '') ) ? '' : $cat_parents;
Hopefully the WP folks will fix this problem, but until then, at least NGFB will be able to handle it. ;-)
This solution came from http://wordpress.org/support/topic/catchable-fatal-error-object-of-class-wp_error-could-not-be-converted-to-string-11?replies=17.
Please download and install the latest DEV version from http://downloads.wordpress.org/plugin/nextgen-facebook.zip again, and let me know the results.