I made some progress today. I formatted the flash drive as FAT32 before starting the process and it seems to work now. It's weird that I had to do this on a brand new flash drive, especially since the process says it is formatting the drive, but it works now.
I tried formatting using quick format on the SP (right click on the drive in Explorer and choose format).
I created the recovery drive using the tool again (search for "recovery" from the charms bar and select "Create a recovery drive" from the settings list).
I still get the same error.
I ordered this SP from the US and got it couriered to Thailand. I got it last week.
Couriering back to the US for a replacement, and then couriering the replacement back here will be incredibly expensive.
I haven't tried a full system reset yet, but haven't the time at the moment. Maybe on the weekend.