It fixed your problem because it cleared all the program data (note: not the actual program itself--you could have 10,000 apps and still never get the low on space if none have data) from all your apps. You don't need to factory reset. Just follow some of the advice in the thread linked above.

Some of the big problem apps are messaging (for sms/mms), internet cache, emails, game data. I also heard Netflix stores a ton in the /data/data folder.

For some reason HTC thought at the time that app data would never surpass 150mb. Since then the Android Market exploded and that is obviously not enough anymore. All HTC phones after the Incredible haven't had this problem so they quickly realized their mistake. Unfortunately, no software update can ever fix this for Incredibles since the space is permanently set in a partition which can't be touched. Gingerbread got around this a little bit by allowing certain files to move outside the data/data folder but I have heard it's not enough.