Perhaps your issue is similar: maybe your machine has more than one public IP, and bitcoind is publishing the one that doesn't accept connections on port 8333.
While I do have a dynamic ip, it has remained the same for over half a year at least. So this is not my issue. I also tried to download the currently latest stable version of bitcoin for Linux (0.3.24) and tried running both the 64 bit and 32 bit binaries. It still didn't work. Moreover, I tried to run ./bitcoin -testnet and forwarding port 18333 as well. When I run the client in testnet mode, it gets zero connections and consequently does not download the testnet blockchain at all. I tried telneting from a server outside of my client's ISP, and it showed one connection. When I exited the telnet session, it showed 0 connections again. So the port forwarding works. But what could be wrong with my setup, when the "main net" always shows at most 8 connections and the testnet shows at most 0 connections?
Edit1:
Here is the output from the logfile (tail -f ~/.bitcoin/testnet/debug.log): https://gist.github.com/1121785