I did TAT last summer..

Surfy,
Using a small 4x4 is doable but will not run through very few trails such as Poucho Spring rd as it is ATV trails. And few trails west of Richfield, UT is atv trails that I don't think 4x4 will be able to get through but other than that- doable for 97% of the trip.

Tony,
I took KLR650 and if I was to do it all over again, I would take a lighter bike. 250cc to 400/450cc and that is sufficient. Yes KLR650 was a good bike to use but in some area I wished I had a lighter bike.

I rode solo so here are few advices: Buy map early on (I took the trip very last min with 1.5 weeks of planning) and study the routes. Mark different highlight color for 'loop'. You will thank me when you get tired of doing loop and especially when you find yourself behind in schedule and feel loop is waste of time. If you don't like to ride red 'difficult' trail, let me know and I can tell you few passes that are difficult especially if riding solo so you can decide if you want to do it or pass. I had a bad crash halfway of Eagle Pass then I had a hard time getting out I was cursing under my breath.

I would definitely do it all over again but there are few trails I will not do again because I like riding solo and few trails are not safe (in my opinion) for riding solo. I would take a lighter bike and I would do the trip late May to early June so you can avoid hot summer heat. I did it in July.