Your idea about this being related to your sinuses is a good one. Buy some decongestant nose drops from your local pharmacy. Next time you fly sniff one drop up each nostril 30 minutes before take-off and 30 minutes before descending. This should open the sinuses and prevent the pressure build up.
Hope this helps