I saw an older thread someone asked the same question. The answer given was to set the permalinks in the New Blog Templates. I couldn't find the settings in this plugin. Also, what about sites that aren't created through this plugin?
I must be missing something simple, but I guess I never had to deal with this before for my user sites. I looked in the super admin settings and on individual sites' settings, but I can't find the permalink settings area anywhere like I do on a non multi-site installation.