I had one large group of emoticons and of course users could not find beyond the first 21.

So I created a new group and moved "extra" ones to that group.

Now somehow the extra group is first in list in ACP and to users. 

I can't find a way to change the order of categories.  What am I missing?

It should be drag and drop. It's the only one that doesn't have the move icon when you mouseover the header. So grab it and drag it and drop it to the place you want.