Don't panic. Your photos are not gone.
When you start shooting, photos are named from 1 to infinity. When you restore your iPhone to factory default (or DFU mode install) and upgrade to iOS 4.0, naming sequence is reseted (even if you restore your settings back) and photos are named back from 1-infinity. Basically your photos in camera roll are now sorted as follow:
iOS4.0 install date -> now -> date of first photo I ever take -> last photo before iOS4.0
So just scroll through Camera roll and you should find your missing photos near top.
iPhone is probably messed up from this situation (gaps between photos or same indexes) and this is reason why library is rebuilded.
To sort this issue out, sync your photos with computer (not via iTunes but with Import photos in Windows or with iPhoto or Image capture on Mac). Choose to erase photos from device. After you do this, camera roll on iPhone will be empty and all your photos will be in your PC/Mac. Now it is the time to sync iPhone with iTunes. Go to Photos tab and Choose "Sync photos from" and choose folder where are your photos located on PC/Mac. After sync there will be one or more photo albums in your Photos app in iPhone and empty Camera roll. When you start taking new photos, they will be placed to the Camera roll.
This should fix problems with rebuilding library, problem with sorting and greatly increase speed of next sync.
Details about importing photos from iPhone to PC/Mac and syncing them back to iPhone via iTunes can be found here:
http://support.apple.com/kb/HT3603