WordPress 2.5.1 Database error – wordpress.wp_post2cat

In the last few days I started getting these database errors whenever I write a new post. The post is added to the database and appears on my blog. I tried deactivating my plugins but the error still happens. I get the first notice while I am writing the post and the second one when I publish the post. Any ideas on how to fix this?
Error #1
WordPress database error: [Table ‘texbiker_net_-_wordpress.wp_post2cat’ doesn’t exist]
SELECT cat_ID AS ID, MAX(post_modified) AS last_mod FROM wp_posts p LEFT JOIN wp_post2cat pc ON p.ID = pc.post_id LEFT JOIN wp_categories c ON pc.category_id = c.cat_ID WHERE post_status = ‘publish’ GROUP BY cat_ID

Warning: Cannot modify header information – headers already sent by (output started at /var/www/html/blog/wp-includes/wp-db.php:216) in /var/www/html/blog/wp-includes/classes.php on line 788

Error #2
WordPress database error: [Table ‘texbiker_net_-_wordpress.wp_post2cat’ doesn’t exist]
SELECT cat_ID AS ID, MAX(post_modified) AS last_mod FROM wp_posts p LEFT JOIN wp_post2cat pc ON p.ID = pc.post_id LEFT JOIN wp_categories c ON pc.category_id = c.cat_ID WHERE post_status = ‘publish’ GROUP BY cat_ID

WordPress database error: [Table ‘texbiker_net_-_wordpress.wp_post2cat’ doesn’t exist]
SELECT cat_ID AS ID, MAX(post_modified) AS last_mod FROM wp_posts p LEFT JOIN wp_post2cat pc ON p.ID = pc.post_id LEFT JOIN wp_categories c ON pc.category_id = c.cat_ID WHERE post_status = ‘publish’ GROUP BY cat_ID

Warning: Cannot modify header information – headers already sent by (output started at /var/www/html/blog/wp-includes/wp-db.php:216) in /var/www/html/blog/wp-includes/pluggable.php on line 694