Блин уже не понимаю, что не так. Сперва пытался удалить через код который был изначально написан в условии - но вылетала ошибка. Потом попробовал через итератор - такая же фигня. Кто подскажет может?
public static void removeItemFromMapByValue(Map<String, String> map, String value) {


       Iterator<Map.Entry<String,String>> iterator = map.entrySet().iterator();
       while(iterator.hasNext()){
          Map.Entry<String,String> entry=iterator.next();
          if (entry.getValue().equals(value)) map.remove();
       }

        /*Map<String, String> copy = new HashMap<>(map);
        for (Map.Entry<String, String> pair : copy.entrySet()) {
            if (pair.getValue().equals(value)) {

                map.remove(pair.getKey());
            }
        }*/

    }