pstoreするときだけ外部エンコーディングの影響をなくしたこれなら動く
当たり前だが

# coding: utf-8
require 'pstore'
db = PStore.new("pstest")
str = "あいうえお"
@evacuated_encoding_for_pstore = Encoding.default_external
Encoding.default_external = Encoding::ASCII_8BIT
db.transaction{ db[1] = str }
db.transaction{ puts db[1] }
Encoding.default_external = @evacuated_encoding_for_pstore

puts してるのは UTF-8 エンコーディングの UTF-8 バイナリ列のままだから
コマンドプロンプトでは化けるので注意