Ok, a bit of sad news, I wasn't able to figure out what was using all the space. I did figure out that the "Phone Storage" is the /data partition, which wasn't readable. I tried just about everything, all the way down to adb shell, but couldn't read it. It hurts that I couldn't install busybox to get a set of proper commands. I also looked into remote mounting the filesystem in Linux, but ended up just giving up. So, I uninstalled all apps, one at a time, and none of them freed up any of the large chunk of data in /data.
So, I just unlocked my bootloader through HTC. Interestingly, before the unlock/factory reset, I had the notification of the ICS update, but now, when I check for updates, it shows none available. Now I'm unlocked so if this happens again, I'll be ready.
After the factory reset, without updating any apps, or installing any new apps, it shows 107MB used and 2.4GB free.