Database Error, Without the upgrade

Okay, so I got this error in the categories area of admin to write a post or page:

WordPress database error: [Unknown column ‘link_count’ in ‘where clause’]
SELECT cat_ID FROM wp_categories WHERE category_parent = 0 AND ( link_count = 0 OR category_count != 0 OR ( link_count = 0 AND category_count = 0 ) ) ORDER BY category_count DESC

After browsing the forum, I see that a lot of people had the same problem when they upgraded. My situation is a little different and maybe I do need to run some sort of upgrade?

To make a long story short, I tried the one-click installation through Yahoo! Small Business, but it was full of bugs, so I decided to uninstall it, and install the current version of WP myself. Everything seemed to be working until I got the above mentioned error.

This post looked like it was going to have my answer:
http://wordpress.org/support/topic/115353
Until I got to step #9 — I cannot find a table called wp_categories in my database folders….

Any ideas as to what to do? I have install WordPress to different hosts, so I am fairly familiar with it, but am stumped as to what I need to do in this situation.