Apple has routinely rejected apps that attempt to mimic core functions of the OS. So, if you go back and re-read my comment where it says tethering is built-in to the OS, then it would make sense that 3rd party apps that attempt to enable tethering would be banned. This may be "right" or "wrong" depending on your viewpoint, but it would serve to ensure that users are not seeing/downloading apps that don't work or function as they are expected to.

My personal experience with Android apps (Moto Droid and now HTC incredible) is that a decent percentage of apps (mostly (but not exclusively) games and odd things like "LED Flashlight Strobe" type stuff) do not work universally across all devices. Reading the comments on some of these apps supports my personal experience, so I think there is still a general problem with any random app on the Android store not offering a 100% consistent or "functions as expected" experience across all Android devices.