In case anyone else runs into this or wants avoid it, I have my stats key files in Dropbox, any cloud backup (sugarsync, box.net, etc etc) will do. Even a flash drive works, though it's so 2005. The file doesn't change once it's created, so there's no need to back it up regularly.
You should find it in your Xonotic data directory. If you're using Linux it should be in your home directory under /.xonotic, or if you're using Windows you'll see a Xonotic folder it in 'My Games' in 'Documents'/'My Documents.' The file you're looking for is usually 'key_0.d0si'
Once that file is gone, there's no alternative but to ask to have your old stats merged with your new stats. Definitely back up your .d0si file somewhere!
-Edited for correctness on Linux home dir, thanks Mr. Bougo. I was afraid I was off on that, haven't been able to use Linux much lately.