Another stupid error. 
In NoFollow.integrate.php, change:
$message = preg_replace_callback('~<a href="(.*?)" class="bbc_link" rel="nofollow"(?: target=".*?")?>~', array(self::$instance, 'replace_callback'), $message);
to:
$message = preg_replace_callback('~<a href="([^>]*?)" class="bbc_link" rel="nofollow"(?: target="_?\w+")?>~', array(self::$instance, 'replace_callback'), $message);
that should do.