Actually, the Canadian website says 2 weeks:
So whoever you're trying to buy one from - they're messing you around.
If you're in a contract with a carrier, I'd suggest phoning them up and asking to speak with their retentions department. Talk to them about how you're thinking about leaving if you can't get an iPhone 4 soon. Most of the big carriers -- Rogers, Telus, Bell, and even Fido -- have taken orders through their retentions department. It really seems to depend on the day though, whether or not they can sell any. But it's worth a shot!
To be fair though, couple of my friends got one by either waiting in line at the Apple store or calling Rogers retention etc... but I really don't care enough to jump through hoops to get one so I'm still waiting!
My advice is to threaten to switch carriers. They'll take care of you nice and quick.