If you can live with just your contacts backed up, I suggest you do the following. Just delete your backups and restore the phone as new. Since you are already setup in iCloud with your contacts there, as soon as your reconnect the phone to iCloud, your contacts will show up on your phone. If you are using photo stream, most of your pictures should be there and you can save them to your phone. Any apps tied to your main iTunes account can be redownloaded if they aren't already on your computer. Any of your music purchased from iTunes can be redownloaded as well.
I believe the only thing you'll lose will be any application specific data, as well as any profiles or certificates you may have on your phone. If you can live with this, then do what I mentioned above, otherwise, I'm not sure what you need to do.