It may be that you have activated wireless contact synchronization with GMail or some other supported service. If such is the case, what is on the server is the "master", and the Desktop Software will not overwrite it. If you want to do so, you must first disable Wireless Contact Sync for the BB and then the restore process should be able to proceed. Then again, if the server data is fine, then I don't understand why there is a even need to restore via the Desktop Software?
Occam's Razor nearly always applies when troubleshooting technology issues!
If anyone has been helpful to you, please show your appreciation by clicking the button inside of their post. Please click here and read, along with the threads to which it links, for helpful information to guide you as you proceed. I always recommend that you treat your BlackBerry like any other computing device, including using a regular backup schedule...click here for an article with instructions.