I haven't used PostgreSQL and its 'bytea' type, but I think you may need to call DBI::bind_param before execute in order to tell your statement handle explicitly that you're supplying binary data.

Try something like this before calling execute:

$sth->bind_param(2, nfreeze($test, { TYPE => 'bytea' }));
[download]

This may also work:

$sth->execute(nfreeze($test), { TYPE => 'bytea' });
[download]

Be sure to check the value of $sth->errstr, and here are a couple of related threads: Maintaining state through storable.pm? and BLOBs and error ORA-01465

Update: fixed index of param to bind and a typo, and bytea should be SQL_BINARY like diotalevi's example.