I would say that depends on the southern accent in question. I (native english, mid-east coast) have never had trouble with Texan accents at all, no matter how strong, but have had a lot of difficulty with rural accents from people in South Carolina. A few weeks ago I was down there visiting and tried to buy some shrimp from a native South Carolinian. I had to resort to hand-gestures; he seemed to have as much difficulty understanding me as I did him.