Warning:As with all editing of files, you should keep a backup of them before you start to change them. Believe me, it will save some headaches along the way.

Adding the nofollow and external attributes is quick, easy and painless, here are the 3 steps.

open file /wp-admin/edit-link-form.php
Go to line line 193 / 194 and find
<th scope="row"> <?php _e('identity') ?> </th>
Above that add
<th scope="row"> <?php _e('seo') ?> </th>
<td><fieldset><legend class="hidden"> <?php _e('seo') ?> </legend>
<label for="external">
<input class="valinp" type="checkbox" name="seo" value="external" id="external" <?php xfn_check('seo', 'external'); ?> />
<?php _e('external') ?></label>
<label for="nofollow">
<input class="valinp" type="checkbox" name="seo" value="nofollow" id="nofollow" <?php xfn_check('seo', 'nofollow'); ?> />
<?php _e('nofollow') ?></label>
Once you have this, go to Links on the side bar, and now you can change existing links or add new links with these attributes. There will now be an extra line in the Link Relationship section of your Links page.