I've heard good things about cutting tread into Colsons like so:
http://www.team228.org/gallery/125/b...3511-8f172.jpg
I have no concrete evidence that this increases traction, but I know 228, 125, and I think 1477 all cut their tread like this so perhaps someone from one of those teams can chime in here with some data.
In response to Pat's questions about extremely small traction wheels, the only COTS ones I can think of are Colsons and Banebots, and even the hardest (blue) Banebots wheels would have to be changed too often to be worth it. I would at least explore the possibility of cutting treads into Colsons, because the alternatives are machining intensive.