Most of the Japanese people you talk to will tell you that the people of northern Honshu, in the Touhoku area, speak the most difficult type of Japanese. One of my Japanese friends said that when he was up there once he had to get a girl to interpret what an old woman was saying because he accent was so thick.
However, I've just been reading the book "Roads to Sata" by Alan Booth, who walked from the top to the bottom of Japan, and he seemed to think that the people in countryside Hyougo prefecture, in the Kansai region, were the hardest to understand.
I live in Osaka, and the people here are quite proud of their dialect. However, I think it only really differs greatly in casual conversation. In formal speech like in business meeting they use standard Japanese without the slang and colloquialisms.