For those who may happen to stumble upon this thread later on, I ended up fixing the problem I described above! Here's how.
First I noticed that phpMyAdmin was acting very strangely / not working, which tipped me off that something might be up with the database. So I contacted my hosting provider and asked them to look into it. Here is the response I got:
"the error you get was cause by no tmp disk space, you had a lot of mysql cache and session files, we made the new space 4GB instead of 400MB and you should be okay now."
As soon as they did that, all my categories and tags came back and everything was fine.
Upon further investigation, we hypothesized that the reason the tmp disk space was full is because of WP Super Cache. Disabling WP Super Cache plugin before upgrading probably would've helped us avoid this problem at all.