I've lost everything on my iphone4, how do I put my library back? Syncing doesn't work
Are you connecting your phone to the mac / pc you're usually syncing it too? Because it would need the backup file which is created everytime you sync it.

If so, you should try this instructional guide. It has screenshots and should be easy to follow. If this does not work write what's happened.

http://ipod.about.com/od/iphonetroubleshooting/ss/restore-iphone.htm