Multiple resets didn't fix it. I found a post on the main Blackberry forum by JSanders (who I think used to be on this forum) whereby someone else had the same issue. Apparently, if you have extended SMS threads, it will clog up the memory and device usage. I charged the phone fully, deleted a ton of long SMS threads that had photo's attached, and held the power button for 30 seconds which seemed like three consecutive reboots. Afterwards, the phone functioned normally again.
Here's the link:
PS: I noticed there is an OS update for the Classic on Verizon today. It doesn't address this but I would love to submit this problem to them for a future release. However, they did supposedly address an issue with the cached emails which I posted about awhile ago but I haven't tested the new software yet to confirm.