It happens after upgrading to Mac OS X Leopard. I'll tried the same iCal and Address Book with a Mac OS X Tiger 10.4 and it works fine!
The problem: - Occurred after upgrading to Leopard - When turning on the "Show Birthdays Calendar" (in Preferences...) - Changes in iCal, e.g. new entries, amending existing entries, deleting entries, etc., will NOT be saved! - It works again if the "Show Birthday Calendar" is unchecked - It also work with a "small" address book but not a BIG one -- My original one has over 2,500 contacts. If I replace it with a small one, these's no problem encountered.