Finalmente hemos conseguido actualizar al nuevo Wordpress 2.1, y la verdad tiene buena pinta, parece que es algo más rápido. La administración vuela, cosa que antes no pasaba, y muchas veces tardaba mucho en cargar inicialmente o el editor html. Felicidades al equipo de Wordpress por esos cambios.
En mi caso he tenido que crear de forma manual la tabla wp_link2cat en la base de datos.
CREATE TABLE `wp_link2cat` (
`rel_id` bigint(20) NOT NULL auto_increment,
`link_id` bigint(20) NOT NULL default '0',
`category_id` bigint(20) NOT NULL default '0',
PRIMARY KEY (`rel_id`),
KEY `link_id` (`link_id`,`category_id`)
) ENGINE=MyISAM DEFAULT CHARSET=latin1 AUTO_INCREMENT=9 ;
Gracias a la gente de Soporte Wordpress por su ayuda.