VERSIONS: WordPress 2.7 and 2.7.1; PHP version 4.4.7; MySQLversion 4.1.22-standard, Server OS - Linux. Hosting service provider: inmotionhosting.com.
PROBLEM: Categories and Tags disappeared from the WordPress admin, and were not visible on the blog (none displayed in Posts > Categories or Posts > Manage Tags). When editing a post, I could see "Most Used" but not "All Categories." All posts had their categories changed to "Uncategorized" in both Manage > Posts and on the posts in the blog.
I could see the Categories and Tags in the database.
SOLUTION: Restart the MySQL Server.
If you manage your own server, you can restart the MySQL server from the command line. I am a hosting reseller, so I could use the Web Host Manager. If this applies to you, go to your WHM, click Restart Services, then click MySQL Server. If you don't have that access, contact your hosting service provider to restart the server.
WHAT DID NOT WORK: Deactivating all plugins. Upgrading WP (2.7 to 2.7.1, in my case).
My research indicates that this ia a mySQL server problem, not a WordPress problem. A number of other Web posts and forums indicated that a MySQL server restart also worked in their cases.
It remains to be seen if the problem is solved for good, but all is working as it should now.