No personal experience, but it seems like that would be a great time to be on Arkansas's Ozark Highlands Trail (165 miles). There is an audio interview at trailcast.org (#4) that would give you an introduction. That trail also comes off well in the book _Thru Hikers Guide to America_.
A couple friends of mine are planning a week on the Sheltowee Trace trail in March. That's in Kentucky.
Higher elevations of the AT could still have snow then, but maybe lower regions of the Smokies would be ideal in March.
-adam