something that "just works" with the iPhone takes around 4 hours to get working with a Android phone… This instructions + liberal installation of Tunnelblick and Viscosity finally got the HTC Hero to work as a modem for the Mac.
My guess is that the Viscosity tap/tun drivers made the difference – but I'm not sure… Anyway – lot's of dinking around – let's see how long this setup keeps working :(