If you can't find the tire that you need at Elliot Bay Cycles try Rivendell Bicycle Works. They currently have 4 different models of 650b (584mm) tires. RBW has been stockpiling 584 tires for their upcoming Saluki model and yet to be named mixte model featuring this wheel size. Harris Cyclery along with Bicycle Specialties stock tires of this size too. If Grant Petersen has his druthers, 650b (584) wheels won't be quite so obscure.
Curt Goodrich
Minneapolis, MN