In India, language and food, both change every 200km. When you tell this to people who haven't been to India, they usually think you are exaggerating but it's surreal how diverse India actually is.
Here in Northern Belgium, some people might be able to pinpoint your origin down to a 10-20km region. :)
Over a 200km distance, people definitely would have trouble understanding each other without using a common standardised language ("Standard Dutch", which we learn in school), even when "officially" they are speaking the same "language". On TV, people who don't use the standardised language are subtitled.
So, I haven't been to India, but what you describe seems quite natural.