My module adds a CCK field to an existing content type. How do I then modify an existing view to sort using the new field?
You should override the view and change the sort. I have never seen a module that attempted to alter a view defined by another module.