I've had the same problem for a few months. I am not rooted and I reboot the phone about every 2 weeks by taking out battery and re-installing it. My phone was very slow to show home screen and low storage message. I have 430 contacts and about 40 apps that I did not want to delete. Internal phone storage was about 23mb. I did the following and now am running about 78mb free consistently.
1. Moved any app possible to my SD card. menu>settings>applications>manage applications, then choose an app and hold. the application. Select "Move to SD Card" if it is enabled. If you can't move the app, it will not be enabled. There is also an app I downloaded that makes this even easier. It is called "App2SD". This will actually save you a lot of time by only displaying those apps that can be moved to the SD card.
2. Cleared cache- menu>settings>applications>manage applications, then choose an app. If the clear cache button is white, it has a cache stored and, obviously, pushing the button will clear it. If you hit clear data, it will erase any settings or information saved for that app so you may not want to do this.
3. Cleaned out all the text threads that I no longer wanted. (If there was one message in the thread I wanted to keep, I locked it so it wouldn't be deleted) .
I use Handcent for messaging - To lock a message, find the message and touch and hold till you get a menu. Choose the option "Lock Message" and a lock should display beside the message. After locking all the messages you want to keep, go back and select and hold the thread. Another menu pops up, choose Delete. It will ask if you want to delete thread, (make sure the box is NOT checked to delete locked messages). Then select "Delete"to delete the thread except for the locked messages. (Any pictures you should save to your SD card and delete the message)
4. Cleared phone log - open phone, select "Call Log", select menu button, select "Clear phone log"- this will delete all phone numbers you have received or dialed so make sure you save any number in your contacts if you want to keep it.
5. I use gmail and when I checked my deleted items, their were over 1000. I logged into my gmail account on the computer because it was much faster and easier to delete the items from the computer rather than the phone.
6. After all this I still was at 26 or 27mb so as a last resort, I took out the battery in the phone for about 3 seconds and then put it back in. (This is a soft reboot). It doesn't do anything bad to your phone, it is just like restarting your computer.
7. After battery re-installed, I am happy to report I am at 78mb free internal storage.
Hope these instructions help you. I had been searching for months of why my home screen was so slow to refresh.
