Are the foreign key tables still in your Category.def file - at some point in the past your Category.def file was obviously changed - so I wonder whether the thing that initially changed it might have done it again since you put the changes in there?

Edit: Having just reread your post I see that you are just deleting links and not categories. Can you check your Links.def file and see what the fk tables etc contain at the bottom of the file - you should have something like this:

'fk' => {
'lsql_Users' => {
'LinkOwner' => 'Username'
}
},
'fk_tables' => [
'lsql_Changes',
'lsql_Reviews',
'lsql_CatLinks',
'lsql_Verify',
'lsql_Payments'
],