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.