Just to be clear...
You can see the PhotoStream library on both devices? If so does it only show pics taken with the device itself? If so that is rather strange.
Also, if I remember correctly turning on PhotoStream is a go-forward basis. So any pics already in the camera roll are not uploaded; only photos taken after it was turned on are uploaded. (I am going by how it worked at first release... perhaps it uploads pre-existing photos now.)
Oh, and photos only in PhotoStream--no vids.
Michael