For other's reference - yes I could still access posts and view them on the live website - they just had Uncategorised status.
I did have a backup of the database haven't had to go that far.
In phpMyAdmin I tried to view the structure of the Categories table. I got an error message as follows:
#1 - Can't create/write to file '/tmp/#sql_706_0.MYD' (Errcode: 17)
Googling around this implied that the server was having a problem creating or writing to temporary database files, indicating that perhaps (even though the account itself had plenty of disk space) the server or MySQL installation was running low on system space.
I contacted my hosts and reported the error that phpMyAdmin was giving me. 15 minutes later it seems to have cleared up; they had restarted the SQL service on the server (it's a shared server so this wasn't something I could do directly). My website is now showing Categories again on posts and the theme is showing selected Categories in the right place and Category pages are listing the relevant posts.
If you have the same problem I had them if you browse into the ...data_category table in phpMyAdmin, then click the "Structure" tab, this returned an error message. After restarting the SQL service it had cleared and now lists the fields as you would expect. The WP behaviour is back to normal and no actual data about the posts' categories appears to have been lost.