GliderCFI,
Yes, I am familiar with Regions Air. In fact I know the DO there. Many of my friends flew there, and several of Regions/Corporate Air pilots went on to AirTran. Some also moved onto SWA. The upgrade if pretty quick last time I checked. If I were to get back into it (flying that is), I'd probably go there or try for some local cargo gig. Rumor is (Rumor only) that Regions Air might be getting Saabs sometime in the future.
Also, have you tried Averitt? I think you would fly out of BNA or Crossville. I believe their headquarters for the flight dept is in Crossville. Check it out.
Good Luck!