Kitaets, здарова. Столкнулся с той же проблемой. Дополнительно к твоему выяснил, что в среде оболочки Unity-2D команда gvfs-open не открывает ни одну ссылку из файла ~/.local/share/recently-used.xbel с содержанием русских файлов, а вот в Unity открывает. Может дело в среде переменных, которые используют оболочки?
А вот то, что имена русских файлов так выгладят - это нормально, так кодируется URL.