I've generated a few worlds on hard mode and teleported to catacombs and haven't seen any angels yet.
They spawn fine with the spawn item but it appears they wouldn't exist in a normal survival setting.

Moving Spawn issues to this issue, please track that #316