It is possible to run out of inodes on a Linux file system, even if you have free space. The shamefulness of this engineering tradeoff aside, here's a script to (roughly) count inodes like du counts disk space:

#!/usr/bin/python
import os,sys
def get_entry_count(path):
        r=0
        try:
                for e in os.listdir(path):
                        p = os.path.join(path,e)
                        if os.path.isdir(p) and not os.path.ismount(p) and not os.path.islink(p):
                                r += get_entry_count(p)
                        r += 1
        except Exception,ex:
                sys.stderr.write("%s: %s\n"%(p,ex))
        print "%d  %s" % (r,path)
        return r
 
for root in sys.argv[1:]:
        get_entry_count(root)

This code doesn't detect reused inodes (e.g. hard links), but it should be fine for any practical situation in which you've run out of inodes. Note that you can find the free inode count with "df -i".