Just as a note for anyone who comes across a similar experience:
I just attempted to connect via wifi hotspot two friends computers to see if it was my ancient laptop's problem or the phone's. Both computers could see the AndroidTether connection, and then connect to it, but once selecting it any attempt at surfing the net resulted in "You are not connected to the Internet."
Firmware version: 2.1-update 1
Baseband version: 2.6.29-cc1c2268
Kernel version: 2.6.29-cc1c2268 htc-kernel@and18-2 #1
Build number: 1.22.605.2 CL161494 release-keys
Software number: 1.22.605.2
Browser version: WebKit 3.1
PRI Version: 1.28_002
PRL Version: 51920
ERI Version: 5
Rooted using Unrevoked 3. Installed Android Wifi Tether and Barnacle, no other root using programs.
Oh well, I'll figure out eventually.
ED: Like the original poster, I followed the instructions here:
http://code.google.com/p/android-wifi-tether/wiki/Setup_HTC_Desire_Incredible
Tethering is still not working.
ED2: Tethering works now! It seems after doing the last step, all the phone needed was another proper restart. I hope this slightly embarrassing mini odyssey helps anyone else in the future who has the balls to root the Incredible without having the brains.
Make sure you download the Evo 4G dump and place the proper file in the android.tether folder.