Tupelo to Nashville is pretty easy, take the Natchez Trace Parkway. One issue may be finding campgrounds where you want them, but by the time you get there, another 30 miles won't be as big a deal as it will be when you start.
The Harpeth randonneurs have done a nice job mapping viable bike routes in Tennessee. One key route for you is at http://harpethbikeclub.com/Ultra/600K/TN-600K-Spring-Brevet-Map.pdf
(hope they don't mind a direct deep link). I'd suggest you take the Dragon (U.S. 129) from Vonore; the ridges are lower than the Cherohala leg. I'd suggest staying on NC 28 from just past the state line to U.S. 19, where you'll have 5 miles of high speed, divided highway before you can get off on 19 and go through Bryson City to Cherokee. (Try to avoid 8:00/early morning and school's out periods on 19.) From Cherokee, the Blue Ridge Parkway will take you to Asheville, with enough climbing to make up for missing Cherohala. Camping, again, may be an issue, since the BRP is a national park, and the stretch from just outside Vonore (or Tellico Plains) to Bryson City is pretty much surrounded by a national park, with camping allowed only in designated campgrounds, of which there are few.
Check with the Harpeth people (http://harpethbikeclub.com/ultra_page/brevet-rides
, Jeff Sammons and crew) to get a good route from the Trace over to McMinnville. I'm pretty sure you can link a few of their rides together to get from Leiper's Fork, a bit shy of Nashville, over to McMinnville, but I haven't ridden enough up there to know what the recommended routes are.