@Jon - It looks like we're both using themes created by Justin Tadlock. You have Options, and I am using Structure. (I recognized Options in the error message because I considered using it before I settled on Structure.) My website at http://www.cnyradio.com also experienced the same error upon upgrading to 2.8.
Even though we're using different themes, Tadlock used the same line of code in both of them. He probably has it in several other themes too. Unfortunately, he doesn't seem to be aware of the problem, and his latest and greatest theme site -- which still has themes for free -- now requires a $25 membership to access the support forums.
$all_cats[$key] = get_cat_name($all_cats[$key]);
Something in that line of code must have "hooked" into something in the WordPress engine or the SQL database. WP must have renamed it in 2.8 -- but which thing? $all_cats? $key? get_cat_name?
And what did they change it to? I know enough about PHP and programming in general to know answering these 2 questions and making the necessary corrections will solve the problem. But I don't know enough to figure out what those answers are.
Ugh... it's great to have improvements and progress, but it sucks when an update renders the entire site useless thanks to one line of theme code that became obsolete. WP is great in many ways, but backwards compatibility apparently isn't among their top priorities.
If this one little thing caused my site to go down, I just can't wait to see how many of my plugins are now useless.