Joel,
I also replied in the road section. Mitsubishi has a 650 38c tire called Trimline that is very tough and rides nicely on smooth surfaces too. I get them in Japan (they are generic for tourers here) but I haven't seen any other make for 650s. I've ridden them thousands of kms and they've taken a severe beating, so if you can get your hands on some you won't be sorry.