The birthdays calendar is a subscribed one in ical, and currently not able to be synced OTA with Mobile me, this will be correct in 3.0 this summer - this may help
http://www.appleinsider.com/articles/09/03/17/iphone3_0_adds_copy_paste_mms_forusers.html
As a workaround if you are using Mobile me as I do you could export your subscribed birthdays calendar from ical and then import it back into ical, as it will then appear as a regular calendar (you may need to rename it). This will then sync OTA via Mobile me. One point to note because this is not subscribed this new calendar will not update and any changes will have to be done manually, or the process above repeated.
Not perfect, but may be a short term solution for you until 3.0.