Some of the previous answers give you general ideas of what is going on, but let us find out how to do something about it. I know you're going to think this pedantic, but let's start with your filesystem type and discuss each as we've seen them under Linux. The fact that your question is tagged with Linux is important because other *nix file systems support lots of other types. I am not an expert on these individual filesystems, but I can quickly understand detailed articles enough to hit the important parts.
Oliver Diedrich wrote an article entitled "Tuning the Linux file system" that makes a couple of very important points. First, these filesystems put the inodes into a reserved area of the disk that allow them to be cached and accessed quickly. The size of this space is fixed at the time the filesystem is created. That means that in order to increase it, you are going to have to a) mirror the files onto another properly sized filesystem and have a switch over period or b) backup the filesystem, recreate it correctly, and restore the files back.
To find out how you're doing on a particular filesystem, say /dev/sda1, use the
debuge2fs -h command and look for these lines about inodes. My filesystem has about 2.4% of my inodes in use on a 226GB filesystem with 100Gb in use (Ubuntu root disk).
Inode count: 15032320
Block count: 60113214
Reserved block count: 3005660
Free blocks: 32794380
Free inodes: 14658480
Others have said that when the inodes are gone, they're gone. And they aren't kidding. I found a tool called ext2resize that was eventually going to offer this feature, but the author seems to have gotten an interesting day job that takes too much of his time. See the FAQ. Don't hold your breath for ext2/3/4 to support this kind of growth as most in the kernel and filesystem community believe that the really interesting work is in solid state disk filesystems as well as clustered filesystems. The ext2/3/4 stuff is old hat, even if ext4 is fairly new.
Another interesting note is that you can try to optimize for directories containing lots of files. Given that you think you will run out of inodes, you probably have some really long directory listings.
tune2fs -O dir_index /dev/sda1 enables b-tree indexing instead of the standard linked-list model. See the man page for tune2fs or Steve's post over at debian-administration.org.
If you want to remake the filesystem with more inodes, you'll have to use the
mke2fs -N ___ option to mke2fs (see the man page and use
debuge2fs for the default, computed number. Optionally, you can change the inode-to-blocks ratio when you make the filesystem with the
mke2fs -i ___ option to mke2fs. My Ubuntu 10.04 distribution ships with a default ratio of 16384 or, if I read this correctly, one, 256-byte inodes for every 16384 data blocks (at 4KB each). Filesystems for newsreaders get a default ratio of 4096 to 1, which is four times as many inodes.
The last three years has seen a popularity explosion in filesystems. Many are available under Linux although the popular ZFS is only available under Sun's Solaris and FreeBSD. Under Linux, you might consider exploring Btrfs, ReiserFS 3, XFS or JFS. There are also commercial filesystems which take your availability and scalability to heart, but there are so many, you'll have to look here at Wikipedia.
Either make your inode stripe large enough on day 1 to handle your file count or move to a filesystem that can handle the load.