Well, another couple days, a whole bunch more calls and I think some things might be moving along. Today, I actually talked to someone that spoke english and appeared to actually be competent. For the first time, I've received some emails saying that my fulfillment game (PGR3) is shipping, with tracking number, and I also got another email saying I should prepare my console for the next step or something, which is hopefully my shipping box. This is the first time I've received any emails.
On Monday, I also filed a complaint with the Better Business Bureau, and complained to Microsoft customer support (instead of xbox customer support). So maybe those have something to do with it. Or maybe just a coincidence?
Hopefully, I'll get my box soon, and another 360 not much longer after that.