If you restore and setup as new yes all your pictures will be gone. So make sure you have them all on your computer then go ahead and restore and setup as new. You could also try this which will be much more simple. Hook up the iPhone to iTunes and click on the iPhone in the left colum. You can get it in the new iTunes by clicking the little box looking icon on the left side and choose show status bar. Then from the menu choose view then "Show sidebar". Now that you've clicked your iPhone in the right pane go to the photos tab at the end and if it is synced with the computer uncheck sync. Make sure you have all the pictures on your computer then apply and do a sync that will remove all the pictures from your iPhone. Then you want to go into the folder where you keep the pictures you sync to your iPhone from the computer, if you do. Look for the iPod Photo Cache folder and delete it. Then hook your iPhone back up again and put the sync option back on and perform a sync to put whatever pictures back onto it that you want.