On your iPhone, when you go to your calendars and go back to look at the list of each calendar, does it show the Birthdays one in that list of available calendars?
Unfortunately I don't have MobileMe to tell you whether that is the problem or not :S
Unfortunately Birthdays won't show up if it doesn't list that as a Calendar on your iphone. I don't know why it is doing that. Maybe it is a MobileMe problem. Let me know how you go after disabling MobileMe.
That's really annoying as it's useful to sync contacts and calendars wirelessly, so why can't it do simple things like birthdays (which are taken from the contact details anyway so it's the iphone that needs to be able to do it - which of course it can with a normal itunes sync!!!)
This didn't work for me...I'd prefer to only use mobileme to sync the calendars...but can i do a one time sync with itunes to get that ones calendar on there...or has someone figured out a better way yet?