Arkansas is usually nice that time of year. I've been to the Buffalo River, Boston Mountains (Ozark Highlands Trail) and the Ouachitas in late March and had great weather for all.

We just got back from Big South Fork and may be going there again in late March, so I second that as another suggestion.