Finally, the "replacement" came, so I went there, and asked them to test the speed of the replacement.  They said it was still slow, so offered a refund for it.

From reading all those issues where people have had warranty problems, I was expecting it to be a lot more difficult to get a refund, especially since I bought it from a cheap-ish store, but it went fairly smoothly.

So I swapped it in for a branded 8GB USB (cost an extra $4).  Speeds on this drive are interesting - for the same ~640MB file I tested with my 4GB USB:
2KB block size: 80 seconds
64KB block size: 70 seconds

Seems this drive is a lot less sensitive to block size for some reason.
Oh well, it's reasonable.