I can confirm that USB tethering *DOES WORK* on a launch day device.
I picked my phone up this morning and am tethered to it as I type this. I am running Ubuntu 10.04 on the tethered laptop. Ubuntu detected the phone as "usb0" and just worked.
I had previously gotten the same error you all are reporting. Unfortunately I'm not sure what I did to fix it. I encountered the Active Sync reboot loop problem and did a hard reset on the phone, deleted everything on the device, and reformatted the Micro SDHC card from withing the EVO environment. After performing those steps to recover from the Active Sync issue, I noticed that I was no longer getting the Error 67 message.
Good luck!