d = {'0': ['Pyrobaculum'], '1': ['Mycobacterium', 'Mycobacterium', 'Mycobacterium', 'Mycobacterium', 'Mycobacterium', 'Mycobacterium', 'Mycobacterium', 'Mycobacterium', 'Mycobacterium', 'Mycobacterium', 'Mycobacterium', 'Mycobacterium', 'Mycobacterium', 'Mycobacterium'], '3': ['Thermoanaerobacter', 'Thermoanaerobacter'], '2': ['Helicobacter', 'Mycobacterium'], '5': ['Thermoanaerobacter', 'Thermoanaerobacter'], '4': ['Helicobacter'], '7': ['Syntrophomonas'], '6': ['Gelria'], '9': ['Campylobacter', 'Campylobacter'], '8': ['Syntrophomonas'], '10': ['Desulfitobacterium', 'Mycobacterium']}

# Iterate through and find out how many times each key occurs
vals = {}                       # A dictonary to store how often each value occurs.
for i in d.values():
    for j in set(i):
        vals[j] = 1 + vals.get(j,0) # If we've seen this value iterate the count
                                # Otherwise we get the default of 0 and iterate it
print vals

# Iterate through each possible freqency and find how many values have that count.
counts = {}                     # A dictonary to store the final frequencies.
# We will iterate from 0 (which is a valid count) to the maximum count
for i in range(0,max(vals.values())+1):
    # Find all values that have the current frequency, count them
    #and add them to the frequency dictionary
    counts[i] = len([x for x in vals.values() if x == i])

for key in sorted(counts.keys()):
  if counts[key] > 0:
     print key,":",counts[key]

{'Mycobacterium': 3, 'Pyrobaculum': 1, 'Campylobacter': 1, 'Syntrophomonas': 2, 'Desulfitobacterium': 1, 'Gelria': 1, 'Helicobacter': 2, 'Thermoanaerobacter': 2}
1 : 4
2 : 3
3 : 1