Your validation rule likely needs to be on the "LINK" object. When you reference projects in your "Projects" field, you are creating CustomObjectProject links. So, your validation rule should be to block the deletion of these links, at the link level; and, not the objects themselves.
Hope that helps.