Might help if you mention what OS you're running, if your talking strictly about on the phone or in combination with sync'ing. The more information you provide the easier it is for others to help ya.
Posted from my CrackBerry at wapforums.crackberry.com
Not sure if this will help, but if you go to the Calendar, select Options. You should have General Options, Conference calls and Calendars. If you have more than one calendar listed, you may be loading your birthdays to calendar other than the one you are viewing. I had this same issue and kept reloading entire calendars. Finally I stumbled on to this and made sure to keep only one calendar as the default. It had something to do with the three different mail accounts I had set up on my Storm. Hope it helps.
The search links must get reset after a certain time.
All I did was search Key Words: birthday, contact, calendar in the search function and found quite a few posts with info on possibly fixing your problem.