Ug, that sucks - I just took a look. I saw something similar in CTP babylon recently when renaming it to try out a couple texture ideas; it had about 10 different 5 character prefixes.
So, I renamed chunks of the tileset, one prefix variant at a time, using the same tool you're using. I didn't have any underscores to contend with, though. FYI, I just tried the tool and the error message is not precise: it may work for a 5 character prefix, rather than a 5 letter prefix. (It does handle numbers, too) so I suppose you can try this:
1) rename gg_a0* to ge_a0*
2) rename gg_b0* to ge_b0*
3) rename gg_c0* to ge_c0*
so on and so forth until you've covered everything. You may be able to do a partial reskin that reuses some/most resources and only renames the chunks you need renamed, if that's interesting. It depends what you're doing.
-Dave