That happened because photo stream photos only stay in iCloud for 30 days, even though they remain on your phone. When you enabled photo stream on your new phone, only photos from the last 30 days are still available.
If you still have your iPhone 4, save the photo stream photos to your camera roll (unless they are already there) by opening the my photo stream album, tap Edit, tap the photos, tap Share, tap Save to Camera Roll. Once in the Camera roll they can be imported to your computer as explained here: http://support.apple.com/kb/HT4083, then synced to your new phone by selecting them on the Photos tab of your iTunes sync settings and syncing.