Personally, one of the things I love about python is the tuple-dict combination. What you have here is effectively a 2d array (where x = fruit name and y = color), and I am generally a supporter of the dict of tuples for implementing 2d arrays, at least when something like numpy or a database isn’t more appropriate. So in short, I think you’ve got a good approach.
Note that you can’t use dicts as keys in a dict without doing some extra work, so that’s not a very good solution.
That said, you should also consider namedtuple(). That way you could do this:
>>> from collections import namedtuple
>>> Fruit = namedtuple("Fruit", ["name", "color"])
>>> f = Fruit(name="banana", color="red")
>>> print f
Fruit(name="banana", color="red")
>>> f.name
'banana'
>>> f.color
'red'
Now you can use your fruitcount dict:
>>> fruitcount = {Fruit("banana", "red"):5}
>>> fruitcount[f]
5
Other tricks:
>>> fruits = fruitcount.keys()
>>> fruits.sort()
>>> print fruits
[Fruit(name="apple", color="green"),
Fruit(name="apple", color="red"),
Fruit(name="banana", color="blue"),
Fruit(name="strawberry", color="blue")]
>>> fruits.sort(key=lambda x:x.color)
>>> print fruits
[Fruit(name="banana", color="blue"),
Fruit(name="strawberry", color="blue"),
Fruit(name="apple", color="green"),
Fruit(name="apple", color="red")]
Echoing chmullig, to get a list of all colors of one fruit, you would have to filter the keys, i.e.
bananas = [fruit for fruit in fruits if fruit.name=='banana']