Most of my categories have disappeared today. This morning they were fine, this afternoon, all of a sudden, most are gone from the category list.

When I go to items, I can see items with the missing categories named, but then when I click on the item, I get the following message:

Gateway Time-out

The gateway did not receive a timely response from the upstream server or application.

From the front end - everything is fine, items from the missing categories are pulling up. Any ideas?

Try repairing your DB tables.
If you don't have access to the DB, there are several extension which perform this task.
Admin Tools is one of them.

Also try clearig Joomla!'s cache.

I've done both of these and the categories are still not showing. I forgot to mention that it's only K2 categories that are affected - the regular joomla categories are fine.

Are the categories present in your DB?

And just stating the obvious. You have reset your filters to show published categories, right?