I have uploaded videos to You Tube in the past but the last two times I tried I received a message that it was not the correct format. I got the same result trying to upload to facebook. Any suggestions?
Without knowing which version of Photostory you are using we are only guessing.
I would hazard a guess that you are using an older version of Photostory and Youtube and Facebook have a habit of occassionally updating the upload API's to use newer file formats or add features, this breaks older software.
Try exporting the video as mp4 using the recommended settings from Youtube and Facebook (under Technical questions section).
Tthen upload using the Youtube or Facebook websites uploaders, ie not from Photostory.