OK, I've been having a play with this and I've found a solution to the problem. It's not perfect (but then what is!).
Here's what you do:
In iCal, select Publish on your Birthdays calendar. You can then select several options such as publishing changes automatically, publishing alarms, etc
Once you click publish, it will start publishing to MobileMe and give you a URL. You can
subscribe to this published calendar in iPhone OS 3.0: go to mail accounts and add. Select Other and "Add Subscribed Calendar". Add the relevant details in there (e.g. the subscription URL), and the Birthdays calendar will appear on your phone.
Now, if you make any changes to contacts in Address Book, the birthdays calendar will update and publish the changes back to your phone. If you change a contact on your phone, it will push back to address book, which will update the birthdays calendar and push it back to your phone.
So far so good - it all works beautifully. So, where's the catch? The only one I can see is that I can't find a way to password protect a calendar published on MobileMe, so if you are concerned about privacy of a birthdays calendar this isn't the solution for you. If you're not, then it should be what you're looking for