I agree with Doc - it sounds like you need to do a reset. If you can set up an appbrain account, that will help you re-download your free apps (the market will remember your paid apps)
Also, check to make sure your contacts are stored in Gmail and not on the phone. If they are stored on the phone do an export to your SD card from the contacts app.
The OEM's and carriers try to do all they can to prevent a reset from being necessary, unfortunately they can account for every possible variable. Sometimes it just needs to be reset.
Hope this helps.