There is an awesome app in the app store called ContactSync. With one press of a button it backs up your contacts to their server, where you creat a username and such, and if you lose your contacts open the app and hit sync and it syncs them back. Best of all the app is free and so is the service on their website.
Its also wirelessly and doe not require you to connect to a computer.