I've done full wipes, stock roms, custom roms, all with the same results.
OK, why not trying to edit build.prop file with a tool like Root Explorer in R/W mode - open it and find the ro.product.locale.region and change it to US if it is different. Save the file and restart the device. Alternatively you can try Market Enabler.