I played around a little more in the WYSIWIG settings and found that if I removed the clickable box and changed WYSIWYG Smilie Menu Total Smilies from the original 15 to the total number of smilies, then I could pick one from any category. The problem is that I have almost 1000 smilies (which is why I needed the category hack in the first place) and setting the menu total to 1000 makes the postbit load at a snail's pace.
So it's obviously not even close to a solution, but hopefully this experiment might you a better idea of how to procede towards a fix. I truly love this hack, Pseudomizer, and I very much hope you can pinpoint the problem. Until then, I'd far rather have my categories than the WYSIWYG editor.