Treebound - Take a look at a Surly LHT in 56cm - a new frameset can be had for under $400. If you get one in black, this leaves you with the option of substituting an aftermarket disc fork (almost always in black, too, with an a-t-c of 395-400mm) for a not-too-expensive brake upgrade. All LHTs have 46cm chainstays, the longest you can get in a new (non-custom $$$$) touring frame nowadays. The rear dropouts are spaced 135mm even on 700c frames, so you can build wheels with mtb hubs for a little less dish. This is a very good tourer for relatively low cost.
http://surlybikes.com/frames/long_haul_trucker_frame/
For ~$200 more you can get a Salsa Vaya, which will cost about the same to build up, using more powerful Avid BB7 brakes in place of cantis or Vees. The Vaya has an advantage over the LHT in that it's offered in 54 55 56 57 58 cm sizes (LHT is 54 56 58) so a better fit may be possible. The Vaya has 45cm CSs. This is a more costly option than the LHT, but it is a pretty fancy tourer in the end.
http://salsacycles.com/bikes/vaya/
From what I can tell, the Fuji Touring has 44cm CSs, just so you know. It appears to be identical to a couple models offered by BikesDirect, a reputable low-cost bike e-tailer. You can get a 54cm Motobecane GT (55.5cm ETT) shipped for $700. This is a pretty good deal considering it includes Tektro Oryx cantis and levers, Sugino XD600 crankset, Shimano DA barcon shifters, Shimano HG50 cassette, Wellgo pedals with clips and straps, Shimano Tiagra FD and Shimano XT RD. These items alone cost $500 as parts. So you're getting the frameset, wheels, stem, hbar, tape, saddle, seatpost, BB, headset, rack, cables and housing for $200. Again, this bike has 44cm CSs, as do many bikes sold as "tourers" these days (42.5-44 is common). Not an ideal solution, but probably your best deal unless you're willing to wait for a highly motivated seller with the perfect sized, good condition used bike. The LHT or Vaya would cost you an additional $200-400 to build.
http://www.bikesdirect.com/products/...an_turismo.htm
Bear in mind that decent racks, panniers, clothing, camping gear, safety items etc necessary for touring will add several hundred dollars cost. It basically costs you >$2,000 before you ever hit the road, which shouldn't surprise you. Since you already own several bikes and a BOB trailer, you're already basically equipped to tour for no additional expense, right?