Well, I managed to find a working version of 0.3.22 to run. It was meant for centOS, but seems to work on debian without a problem. I have yet to test RPC calls though.
The version I am using was downloaded from this post:
http://forum.bitcoin.org/index.php?topic=685.msg371171#msg371171Why is it such a problem to run bitcoind on Debian and so many other headless linux OS's? From what I have read, it seems like the dependencies are not something you can upgrade - it's part of the core OS. It seems silly to have such dependencies that exclude so many linux OS's from running bitcoin...
I could be wrong, and if I am, I would very much appreciate someone pointing out how it might be possible to run one of the later versions of bitcoind on debian.
The issue here is that your libc isn't new enough for the precompiled binaries - they were compiled against a newer version of libc. libc is the C standard library, so anything written in C or C++ (basically everything) depends on it, so it's hard to upgrade.
Anyway, what's confusing me is that I'm running debian stable on my desktop right now, and bitcoin runs fine. I checked the package repos, and all the libraries are a new enough version.
Are you sure you're not on oldstable? Try running:
cat /etc/issue
If you're running stable, it should say "Debian GNU/Linux 6.0"
If it says 5.0, then you're running oldstable, and that's your problem. You're probably going to need to upgrade to stable sometime anyway, and that would let you run the precompiled bitcoind just fine.
Another option is to compile the binaries yourself. It shouldn't be too hard since you won't need UPnP or wxwidgets.
The reason why the centos binaries work is because centos also has an older libc, so compiling against that older version lets it run on your system.