Photos stream not delivering photos from old device to new
Photostream is a funny one, I have spent some time looking at the workflow so I think I know what is happening here.

When you take a picture with an iOS device (assuming wifi etc): 


It is uploaded to the iCloud.
It is stored there for 30 days.
During those 30 days it will be pushed to other photostream devices (iOS, OS X).
After 30 days it is 'purged' (deleted) from the iCloud servers.


Some points to note:

Although it is purged from iClouds servers it will STILL appear in the photostream album on your iPhone.

Thus take this example:

If I take 50 pictures on my iPhone 2 months ago, and 2 new photos today. and then bought a Brand new iPhone and signed into iCloud the following would happen,

On my original iPhone the photostream album would have 52 photos.

On my new iPhone only the 2 photos taken within the last month would push down to the phone.

Some extra points.


I guess this is why Apple says photostream doesn't count towards iCloud storage! They only store items for 30 days.
Although photos may no longer be in the cloud devices still sync - ie if you delete an old photostream photo (older than 30 days) on your iPhone it will delete on any other device that it synced to during the original 30 day period.
iOS only holds your last 1000 photos in it's Photostream album, to keep a photo forever you must save to camera roll, OS X (iPhoto, Aperture) holds them all.
A nice example of this behaviour was when I first got Aperture on my mac, I couldn't understand why so many of the photos in my iPhones 'Photostream' album were not syncing across, check the dates on the photos and you will see!


Finally You can manually add photos from iPhoto, Aperture, or the Windows desktop to your photo stream. You may want to do this if you’d like to add photos that don’t appear in your photo stream automatically. 

http://support.apple.com/kb/PH2606

Additionally, after you asked this question, Apple has documented some of the photo stream limits, but you should be well under the volume of photos that would be capped to enter the stream assuming they were all recent photos and no device exchange in the middle.

http://support.apple.com/kb/HT4858