This isn’t a complete fix as the problem seems to be slightly deeper. Although this fixes catagories not displaying they will still report erroneous numbers of posts within them – always zero.
The same can be seen on the administration interface in the category section. More annoyingly when deleting a category or adding a post to a category gives me this error:
Warning: implode() [function.implode]: Invalid arguments passed in .../wp-includes/taxonomy.php on line 2799
Looking for that section it appears to be a function called _update_post_term_count which is generating an SQL query for later use and it causing the script to fail.
As for how to fix it I have no clue :/