I've a pretty big head, and at one point a long time ago I was in a car accident where I probably had a depressed fracture of the skull. I had a 5 or 6 year old helmet which gave me a headache every time I wore it. It started where I had the head injury and eventually spread to the whole right-side of my head.
At the end of last year I took up cycling quite seriously and got a Specialized max helmet, which is a funny looking object, designed for big heads and relatively cheap. I haven't had a headache since, in fact I hadn't even thought about it for months until reading your post.
The point isn't to rush out and buy a 'Max' but that all helmets are not the same- and fit is very important.