As an AmE speaker, I can say there are only a few very strong regional BrE accents that cause any confusion. The vast majority of BrE accents give us little if any pause. Occasionally there are a few minor vocabulary differences that cause a moment's confusion until you can work out the meaning, but those are pretty rare. Particularly with so much modern-day exposure of international media, many of the common differences are well-known enough to not even register any more.
Of course there are noticble differences, especially with vowels and syllable stress, but I wouldn't classify those as 'strange'.
I worked with a guy from I belive it was Birmingham once, (might have been Yorkshire) and I did have a fair amount of difficulty understanding him. Not sure if it was the accent or just his manner of speaking, but he always spoke like he had a mouth full of pebbles. I spent much of our conversations trying to work out where one word stopped and another started.
I did happened to overhear some other BrE colleagues mocking (rather cruelly) his speech, so apparently it wasn't just my AmE ear that had problems understanding him.