Any process that stops, prevents or reduces the frequency, rate or extent of cellular protein localization. Cellular protein localization is any process in which a protein is transported to, and/or maintained in, a specific location and encompasses movement within the cell, from within the cell to the cell surface, or from one location to another at the surface of a cell. [ http://purl.obolibrary.org/obo/go/references/0000058 ]