How is frostbyte so fast?
I highly doubt they are using 400+ bones (in other words, source please). 9-15k tris I can certainly see though. This thread lists two of the characters as having over 15k tris.
Also I noticed that the number of faces on the rigged mesh is a lot less important than other parameters like the number of bones.
I tried the new lod feature on the mesh which decreases the poly count of characters from over 1k faces to about 200, but it has almost no positive effect on the framerate. After all I hope multithreading for animations will be supported in the next Blender release. There is already a build available with this feature which increases the framerate indeed a lot, but unfortunately crashes really often.
You should grab a build from http://builder.blender.org and see if you’re still getting crashes. If so, you should create a bug report. Otherwise the odds of the crashing getting fixed before the next release are low.