Disclaimer
Rooting your phone may void your warranty. Back up your data before doing this. Also know that I haven't been terribly rigorous in understanding everything that is happening here. You could say that I am cargo cult-ing some of the instructions. For me, since I am due for a phone upgrade, the worst case scenario is that if I brick my phone, I'll head to the Apple store and pick up a 4S.
Overview
What this will do is give you root access to the phone. This will allow you to run custom ROMs. Once you have this, you can replace everything on the phone with something like CyanogenMod. For the time being, I have chosen to stick with the OS shipped on the phone but booted into a custom ROM to fix the issues I am seeing.
The "Phone storage space is getting low" message is caused because application files and some data is stored on a partition that is 150MB. It's mounted to /data/data. Once your apps or that data hist 140MB, you'll get the error and your phone will shut down sync services, meaning you won't see new emails. I found a ROM that repartitions this space to 750MB and haven't had a problem since (roughly a month).
Gaining Root
I use a Mac at home and used Unrevoked 3 to gain root access. The latest version of the software (3.32) did not work in attempting to gain root. I got an error message stating that the firmware was too new. I was able to pull down version 3.22 by changing the download URL. That worked fine. You'll need root access to boot the phone into custom ROMs. You'll need custom ROMs to do the repartitioning.
Repartitioning
I bought a copy of ROM Manager from the Play Store. This will let you boot custom ROMs. I used it to boot the Convert2Ext4_no_data_limit_normal_dalvik ROM. You can find a description of what the ROM does and other variants of it in this XDA Developers forum post. You will need to move the ROM image to your phone to boot it. I just downloaded it to my Mac, mounted the phone's SD card as a disk and copied it over.
Success
After you run the custom ROM, your phone should now be repartitioned and the low storage space error message should go away. With root, you should be able to do other nice things like remove Verizon bloatware. I haven't tried that yet.
Text Messaging
After rooting and repartitioning the phone, I noticed that I could send text messages, but I couldn't receive them. This seems to be a relatively common problem among people who do this sort of thing. After some Googling, I came across this post in the Verizon community forums. Basically, if you go to http://dl3.htc.com/misc/inc8049.apk on your phone, it fixes the issue and you can get text messages again. I have no idea what the file does, so download at your own risk. It goes to HTC, so I figured it was relatively safe.
