I had the same thing happen to me. the verizon peeps couldn't help at first, just sent me a new droid x and the same thing happened with new phone. They got to the bottom of it. It was my sd card. had to reformat it and then all was fine.
the reason for it was a corrupt file had been saved to the sd card and whenever i turned on the phone (new or old one) the phone read the corrupt file! Any app that was on the sd card appeared to have disappeared! They were there but unable to be read! Very annoying and it is a known problem with android, but seems only 1 verizon person knew about it! Thank god i ended up talkin to him after about 10 others who didn't have a clue!
had to post somewhere on the www so it may help someone else cuz it was so frustratin!!
btw....if your phone is acting up, DONT power off by the normal way, do a battery pull so it doesn't save the file to the sd card! i guess when ya power down it saves a backup of all your settings including any problem files!!