My LANG is set to uk_UA.KOI8-U. The default filename for the screenshots is chosen in Ukrainian, which makes sense. However, the actual filename created is never converted from UTF8 to KOI8-U leading to rather nasty filesystem entries.
Never mind. Apparently, gtk (or glib?) is to blame -- it ignores $LANG insisting on the users using G_FILENAME_ENCODING. Once I added G_FILENAME_ENCODING=KOI8-U to the environment, the filenames became correct...