If I want to change category names in DL, will the changes automatically get propagated to Address Book and iCal, or will new categories be added to those applications without deleting the old ones?

Hello.

It will rename the calendars in iCal, but it will create new AB groups in AB.

Can I then safely delete the old AB group?

Yes, you can delete them. If DL still needs it the group will be recreated.
The reason we do not delete them ourselves is because we don't have a 1 to 1 correlation between category and group, it is safest if we just leave them intact in case you are using them with other programs or for other uses.