Solution to basic unit tests
Bug: The result of check_prefix depends on the order of values. Basically, it compares each pair of values once, but truncates only one of the two for comparison. On my Python 3.5 your test fails occasionally.
Duplicate values are also prefixes of one another. It is not necessary for is_consistent to check for both.
It is not necessary to handle the empty phonebook as a special case in is_consistent as the check functions return True swiftly anyway in that case. Thus the function can be simplified to

def is_consistent(self):
    return self.check_prefix()

A more efficient solution for check_prefix would be to sort the values and compare adjacent ones. Making use of pairwise from Itertool recipes, and the fact that the prefix will sort first:

def check_prefix(self):
    return not any(b.startswith(a) 
                   for a, b in pairwise(sorted(self.get_values())))