My host took it upon themselves to change the permission settings on my site so now I can no longer create a new item or category without a fatal error.

Is there a list of what permission settings are needed for K2 to function properly?

What's the error you are getting?

Fatal error: Call to undefined function mb_internal_encoding() in [my server address]/components/com_k2/tables/k2category.php on line 80

I tried uninstalling K2 and re-installing but when I try to create a category, I get:
Fatal error: Call to undefined function mb_internal_encoding() in [my server address]/components/com_k2/tables/k2category.php on line 92


**edit**
I noticed in another similar thread that someone pointed out Multibyte string support had to be enabled. Mine is not. I'm also not sure from the thread if after multibyte string support was enabled the issue was solved. My K2 information panel says Multibyte string support is disabled and if I check phpinfo.php I show something called Zend Multibyte Support. Is that the same thing?

No. It's not the same thing. Since K2 tells you that it is disabled you need to enable it. The error has to do with this.