Pessoal, antes eu tava com problema de TimeLimit, mas consegui resolver. O problema é que agora não to conseguindo contar as calls ;s. Segue o código:

d = {}
def fib(n):
    global cont
    cont += 1
    if n in d:
        return d[n]
    if n < 2:
        r = n
    else:
        r = fib(n-1) + fib(n-2)
    d[n] = r
    return r

n = int(raw_input())

for i in range(n):
    a = int(raw_input())
    cont = 0
    f = fib(a)
    print 'fib(%i) = %i calls = %i' % (a, cont, f)

Se alguém puder dar uma luz eu agradeço