I've experienced this to different degrees in my travels. One time it felt like I was being stabbed in the brain with an ice pick for the entire 6 hour cross country flight and no amount of blowing/swallowing/yawning would help.

It's a form of Eustacian tube dysfunction:

http://en.wikipedia.org/wiki/Eustachian_tube#Disorders

My ENT recommends taking a hit of Afrin nasal spray during takeoff and again just before descent.