Ha!
Here is proof that I write the untidiest code EVER!
I got it to work, Skunk..just about.
Code:
// LinkCounter
mysql_connect($site, $username, $password);
$remove = mysql_db_query($dbName, "UPDATE categories SET linkcount = '0'");
$result = mysql($dbName, "SELECT * from categories");
$num = mysql_num_rows($result);
$i = 0;
while ($i < $num) :
$catids[$i] = mysql_result($result,$i,"catid");
$parentids[$i] = mysql_result($result,$i,"parentcat");
$work = mysql($dbName, "SELECT * from links where catowner = '$catids[$i]'");
$numlinks[$i] = mysql_num_rows($work);
$i++;
endwhile;
$d = 0;
while ($d < $num) :
$currentlinks = $numlinks[$d];
$z = 0;
$catfind = mysql($dbName, "SELECT * from categories WHERE parentcat = '$catids[$d]'");
$found = mysql_num_rows($catfind);
if ($found == "0") {
$worker = mysql_db_query($dbName, "UPDATE categories SET linkcount = '$currentlinks' WHERE catid = '$catids[$d]'");
} else {
$totallinks = $numlinks[$d];
while ($z < $found) :
$workingparent = mysql_result($catfind,$z,"catid");
$totallinks = $totallinks + $numlinks[$workingparent];
$z++;
endwhile;
$worker = mysql_db_query($dbName, "UPDATE categories SET linkcount = '$totallinks' WHERE catid = '$catids[$d]'");
}
$worker = "";
$d++;
endwhile;
This script basically checks out the category that you are in, stores the amount of links in a variable, checks out the subcategories, adds the links to the variable and then updates the LinkCount column in the DB.
Seems to work fine for me. Anyone wants it, take it 
I'm sure you guys will find a way of cleaning it up.
I take your point about server load, but as I'll be running this script about once a week as part of our update, it shouldn't be a problem.
Cheers,
You could try and enforce the "business" rule that when you update a category or link you recalculate the category counts by wrapping all the relevent code into a series of functions or classes. This is where classes become handy in a design. This way in your script you don't directly call mysql_query but put the database access into the relevent functions say:
Bookmarks