Gotta love the near-default support recommendation: hard reset your phone. Not saying it wasn't necessary in this case, but it's surprising how often it's the recommendation.
Dashwire is free and can backup contacts, sms, photos, videos, and call logs. If you reset your phone, all your stuff is still on the web, and we'll help bring your contacts, bookmarks, and speed dials back down. Not just about backup though...having info on web enables stuff like PC text messaging, media sharing to Facebook/Flickr/Twitter, visual voicemail, etc.